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

### Authors

- Yon Dourisboure, LaBRI - Bordeaux 1 University

### 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).