Compact Routing Schemes for Tree-Length Delta Graphs and for k-chordal Graphs


Authors


Abstract

In this paper we use the notion of layering-tree introduced by Chepoi and Dragan, to construct efficient compact routing schemes. We obtain a routing scheme for tree-length $\delta$ graphs: graphs admitting a tree-decomposition with small diameter bags. This scheme uses address and local memory of size $O(\delta\log^2 n)$ bits, and for all pairs of nodes, the length of the route never exceed their distance plus $6\delta-2$ (deviation $6\delta-2$). Then we adapt it for $k$-chordal graphs, and we obtain a deviation $k+1$, with addresses and local memories of size $O(\log^2 n)$ bits per node, an improvement on the best previous (SWAT'04). Observe that for chordal graphs ($\delta=1$, $k=3$) both versions produce deviation $4$ and $O(\log^2 n)$ bits labels, also an improvement on the best previous (DISC'02).