Collective Tree Spanners in Graphs with Bounded Parameters |
| |
Authors: | Feodor F. Dragan Chenyu Yan |
| |
Affiliation: | 1. Algorithmic Research Laboratory, Department of Computer Science, Kent State University, Kent, OH, 44242, USA
|
| |
Abstract: | 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 $mathcal{T}(G)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 T(G)mathcal{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)Tinmathcal{T}(G) 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 O(?n)O(sqrt{n}) collective additive tree 0-spanners, any weighted graph with tree-width at most k−1 admits a system of klog 2 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 (2w)(2mathsf{w}) -spanners, and any weighted graph with size of largest induced cycle at most c admits a system of log 2 n collective additive tree (2?c/2?w)(2lfloor c/2rfloormathsf{w}) -spanners and a system of 4log 2 n collective additive tree (2(?c/3?+1)w)(2(lfloor c/3rfloor +1)mathsf {w}) -spanners (here, wmathsf{w} 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 2 n collective additive tree (2w)(2mathsf{w}) -spanners. Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those families of graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|