Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00109
Compact Routing Schemes for Generalised Chordal Graphs
Yon Dourisboure
Vol. 9, no. 2, pp. 277297, 2005. Regular paper.
Abstract
In this paper, we show how to use the notion of layeringtree
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 kchordal graphs, i.e., graphs containing no
induced cycle of length greater than k, the routing scheme uses
addresses and local memories of size O(log^{2} 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 treelength
δ graphs, i.e., graphs admitting a treedecomposition in which
the diameter of any bag is at most δ, the routing scheme uses
addresses and local memories of size O(δlog^{2} 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(log^{2} n) bits per node.
