Elsevier

Theoretical Computer Science

Volume 444, 27 July 2012, Pages 17-27
Theoretical Computer Science

Distributed computing of efficient routing schemes in generalized chordal graphs

https://doi.org/10.1016/j.tcs.2012.01.006Get rights and content
Under an Elsevier user license
open archive

Abstract

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.

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 k1, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus k1.

In order to compute the routing tables of any n-node graph with diameter D we propose a distributed algorithm which uses O(logn)-bit messages and takes O(D) time. The corresponding routing scheme achieves the stretch of k1 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{ΔD,n}) time, where Δ is the maximum degree of the graph. Our routing schemes use addresses of size logn bits and local memory of size 2(d1)logn bits per node of degree d.

Keywords

Routing scheme
Stretch
Chordal graph
Distributed algorithm

Cited by (0)

Partially supported by programs of Conicyt Chile: Anillo ACT88 (K.S.), Basal-CMM (I.R. and K.S.), Fondecyt 1090156 (I.R.), Fondecyt 11090390 (K.S.), Instituto Milenio ICDB (I.R.) and the European Commission through the EULER project (Grant No. 258307) part of the Future Internet Research and Experimentation (FIRE) objective of the Seventh Framework Programme (N.N.).