Collective Tree Spanners and Routing in AT-free Related Graphs
Vol. 10, no. 2, pp. 97-122, 2006. Regular paper.
Abstract 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.