Collective Tree Spanners in Graphs with Bounded Parameters

摘要

In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system of at most μ spanning trees of G such that for any two vertices x,y of G a spanning tree exists such that d _T (x,y)≤d _G (x,y)+r. We describe a general method for constructing a “small” system of collective additive tree r-spanners with small values of r for “well” decomposable graphs, and as a byproduct show (among other results) that any weighted planar graph admits a system of collective additive tree 0-spanners, any weighted graph with tree-width at most k−1 admits a system of klog ₂ n collective additive tree 0-spanners, any weighted graph with clique-width at most k admits a system of klog _3/2 n collective additive tree -spanners, and any weighted graph with size of largest induced cycle at most c admits a system of log ₂ n collective additive tree -spanners and a system of 4log ₂ n collective additive tree -spanners (here, is the maximum edge weight in G). The latter result is refined for weighted weakly chordal graphs: any such graph admits a system of 4log ₂ n collective additive tree -spanners. Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those families of graphs. Keywords Spanners - Tree spanners - Graph distance - Balanced separator - Graph decomposition - Tree-width - Clique-width - Planar graphs - c-Chordal graphs - Message routing - Efficient algorithms Results of this paper were partially presented at the ISAAC’05 conference [14].