Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00109
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.
|
Journal Supporters
|