Compact Routing Schemes for Generalised Chordal Graphs
Yon Dourisboure
Vol. 9, no. 2, pp. 277-297, 2005. Regular paper.
Abstract
In this paper, we show how to use the notion of layering-tree introduced in [], in order to obtain polynomial time constructible routing schemes. We describe efficient routing schemes for two classes of graphs that include the class of chordal graphs. For k-chordal graphs, i.e., graphs containing no induced cycle of length greater than k, the routing scheme uses addresses and local memories of size O(log2 n) bits per node, and the length of the route between all pairs of vertices never exceeds their distance plus k+1 (deviation at most k+1). For tree-length δ graphs, i.e., graphs admitting a tree-decomposition in which the diameter of any bag is at most δ, the routing scheme uses addresses and local memories of size O(δlog2 n) bits per node, and its deviation is at most 6δ−2. Observe that for chordal graphs, for which δ = 1 and k=3, both schemes produce a deviation 4, with addresses and local memories of size O(log2 n) bits per node.
Submitted: October 2004.
Revised: November 2005.
Communicated by Alon Itai
article (PDF)