Compact Routing Schemes for Generalised Chordal Graphs - Dourisboure, Yon (Journal of Graph Algorithms and Applications, 2005)
<!----> In this paper, we show how to use the notion of layering-treeintroduced in [], in order to obtain polynomial timeconstructible routing schemes. We describe efficientrouting schemes for two classes of graphs that include the classof chordal graphs. For k-chordal graphs, i.e., graphs containing noinduced cycle of length greater than k, the routing scheme usesaddresses and local memories of size O(log2 n) bits per node, andthe length of the route between all pairs of vertices never exceedstheir distance plus k+1 (deviation at most k+1). For tree-lengthδ graphs, i.e., graphs admitting a tree-decomposition in whichthe diameter of any bag is at most δ, the routing scheme usesaddresses and local memories of size O(δlog2 n) bits pernode, and its deviation is at most 6δ−2. Observe that forchordal graphs, for which δ = 1 and k=3, both schemesproduce a deviation 4, with addresses and local memories of sizeO(log2 n) bits per node. <!---->