Geodesic
Compact Routing Schemes for Generalised Chordal Graphs
Journal of Graph Algorithms and Applications, Tome 9 (2005) no. 2, pp. 277-297.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2005_9_2_a4,
     author = {Yon Dourisboure},
     title = {Compact {Routing} {Schemes} for {Generalised} {Chordal} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {277--297},
     publisher = {mathdoc},
     volume = {9},
     number = {2},
     year = {2005},
     doi = {10.7155/jgaa.00109},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00109/}
}
TY  - JOUR
AU  - Yon Dourisboure
TI  - Compact Routing Schemes for Generalised Chordal Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2005
SP  - 277
EP  - 297
VL  - 9
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00109/
DO  - 10.7155/jgaa.00109
LA  - en
ID  - JGAA_2005_9_2_a4
ER  - 
%0 Journal Article
%A Yon Dourisboure
%T Compact Routing Schemes for Generalised Chordal Graphs
%J Journal of Graph Algorithms and Applications
%D 2005
%P 277-297
%V 9
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00109/
%R 10.7155/jgaa.00109
%G en
%F JGAA_2005_9_2_a4
Yon Dourisboure. Compact Routing Schemes for Generalised Chordal Graphs. Journal of Graph Algorithms and Applications, Tome 9 (2005) no. 2, pp. 277-297. doi : 10.7155/jgaa.00109. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00109/

Cité par Sources :