Geodesic
Collective Tree Spanners and Routing in AT-free Related Graphs
Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 97-122.

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

In this paper we study collective additive tree spanners for families of graphs that either contain or are contained in AT-free graphs. We say that a graph G=(V,E) admits a system of μ collective additive tree r-spanners if there is a system T(G) of at most μ spanning trees of G such that for any two vertices x,y of G a spanning tree T ∈ T(G) exists such that dT(x,y) ≤ dG(x,y)+r. Among other results, we show that AT-free graphs have a system of two collective additive tree 2-spanners (whereas there are trapezoid graphs that do not admit any additive tree 2-spanner). Furthermore, based on this collection, we derive a compact and efficient routing scheme. Also, any DSP-graph (there exists a dominating shortest path) admits an additive tree 4-spanner, a system of two collective additive tree 3-spanners and a system of five collective additive tree 2-spanners. 
@article{JGAA_2006_10_2_a0,
     author = {Feodor Dragan and Chenyu Yan and Derek Corneil},
     title = {Collective {Tree} {Spanners} and {Routing} in {AT-free} {Related} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {97--122},
     publisher = {mathdoc},
     volume = {10},
     number = {2},
     year = {2006},
     doi = {10.7155/jgaa.00120},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00120/}
}
TY  - JOUR
AU  - Feodor Dragan
AU  - Chenyu Yan
AU  - Derek Corneil
TI  - Collective Tree Spanners and Routing in AT-free Related Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2006
SP  - 97
EP  - 122
VL  - 10
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00120/
DO  - 10.7155/jgaa.00120
LA  - en
ID  - JGAA_2006_10_2_a0
ER  - 
%0 Journal Article
%A Feodor Dragan
%A Chenyu Yan
%A Derek Corneil
%T Collective Tree Spanners and Routing in AT-free Related Graphs
%J Journal of Graph Algorithms and Applications
%D 2006
%P 97-122
%V 10
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00120/
%R 10.7155/jgaa.00120
%G en
%F JGAA_2006_10_2_a0
Feodor Dragan; Chenyu Yan; Derek Corneil. Collective Tree Spanners and Routing in AT-free Related Graphs. Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 97-122. doi : 10.7155/jgaa.00120. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00120/

Cité par Sources :