Article
Collective Tree Spanners of Graphs
SIAM Journal on Discrete Mathematics
• , Kent State University - Kent Campus
• , Hiram College
Publication Date
1-1-2006
Document Type
Article
Keywords
• sparse spanners,
• tree spanners,
• graph distance,
• balanced separator,
• graph decomposition,
• chordal graphs,
• c-chordal graphs,
• message routing,
• efficient algorithms
Disciplines
Abstract
In this paper we introduce a new notion of collective tree spanners. We say that a graph G=(V,E)admits a system of $\mu$ collective additive tree r-spanners if there is a system T(G) of at most $\mu$ spanning trees of G such that for any two vertices x,y of G a spanning tree T\in \cT(G) exists such that d_T(x,y)\leq d_G(x,y)+r. Among other results, we show that any chordal graph, chordal bipartite graph or cocomparability graph admits a system of at most log2n collective additive tree 2-spanners. These results are complemented by lower bounds, which say that any system of collective additive tree 1-spanners must have $\Omega(\sqrt{n})$ spanning trees for some chordal graphs and $\Omega(n)$ spanning trees for some chordal bipartite graphs and some cocomparability graphs. Furthermore, we show that any c-chordal graph admits a system of at most log2n collective additive tree (2\lfloor c/2\rfloor)-spanners, any circular-arc graph admits a system of two collective additive tree 2-spanners. Towards establishing these results, we present a general property for graphs, called (\al,r)$-decomposition, and show that any$(\al,r)$-decomposable graph G with n vertices admits a system of at most$\log_{1/\al} n$collective additive tree$2r$-spanners. We discuss also an application of the collective tree spanners to the problem of designing compact and efficient routing schemes in graphs. For any graph on n vertices admitting a system of at most$\mu$collective additive tree r-spanners, there is a routing scheme of deviation r with addresses and routing tables of size$O(\mu \log^2n/\log \log n)$bits per vertex. This leads, for example, to a routing scheme of deviation$(2\lfloor c/2\rfloor)$with addresses and routing tables of size$O(\log^3n/\log \log n)\$ bits per vertex on the class of c-chordal graphs.