Distributed computing of efficient routing schemes in generalized chordal graphs

作者：Nisse Nicolas; Rapaport Ivan; Suchan Karol^*

来源：Theoretical Computer Science, 2012, 444: 17-27.

DOI：10.1016/j.tcs.2012.01.006

• Routing scheme
• Stretch
• Chordal graph
• Distributed algorithm

Efficient algorithms for computing routing tables should take advantage of particular properties arising in large scale networks. Two of them are of special interest: low (logarithmic) diameter and high clustering coefficient. %26lt;br%26gt;High clustering coefficient implies the existence of few large induced cycles. Considering this fact, we propose here a routing scheme that computes short routes in the class of k-chordal graphs, i.e., graphs with no induced cycles of length more than k. In the class of k-chordal graphs, our routing scheme achieves an additive stretch of at most k - 1, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus k - 1. %26lt;br%26gt;In order to compute the routing tables of any n-node graph with diameter D we propose a distributed algorithm which uses O(log n)-bit messages and takes O(D) time. The corresponding routing scheme achieves the stretch of k - 1 on k-chordal graphs. We then propose a routing scheme that achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3-chordal graphs). In this case, distributed computation of routing tables takes O(min{Delta D, n}) time, where Delta is the maximum degree of the graph. Our routing schemes use addresses of size log n bits and local memory of size 2(d-1) log n bits per node of degree d.

• 出版日期2012-7-27
• 单位INRIA