0

0

 I.: Collective tree spanners of graphs
 摘  要: In this paper we introduce a new notion of collective tree spanners. We say that a graph G =( V, E) admits a system of µ col- lective 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 any chordal graph, chordal bipartite graph or co- comparability graph admits a system of at most log2 n collective addi- tive tree 2-spanners and any c-chordal graph admits a system of at most log2 n collective additive tree (2� c/2� )-spanners. Towards establishing these results, we present a general property for graphs, called (α, r)- decomposition, and show that any (α, r)-decomposable graph G with n vertices admits a system of at most log1/α 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.
 发  表:

 论文统计图 .axis path, .axis line { fill: none; stroke: #000; shape-rendering: crispEdges; } .line { fill: none; stroke-width: 1.5px; }
 共享有10个版本  [展开全部版本] [收起版本] http://citeseer.ist.psu.edu/cache/papers/cs2/305/http:zSzzSzwww.cs.kent.eduzSz%7EdraganzSzSWAT04.pdf/dragan04collective.pdf http://citeseer.ist.psu.edu/cache/papers/cs2/305/http:zSzzSzwww.cs.kent.eduzSz%7EdraganzSzSWAT04.ps.gz/dragan04collective.ps.gz http://citeseer.ist.psu.edu/compress/0/papers/cs2/305/http:zSzzSzwww.cs.kent.eduzSz~draganzSzSWAT04.ps.gz/dragan04collective.ps
 Bibtex @ARTICLE{author = {Feodor F. Dragan and Chenyu Yan and Irina Lomonosov},title = {I.: Collective tree spanners of graphs},journal = {SIAM J. Discrete Math},year = {2006}}

 还没有人点评哦

 k -Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees Collective Additive Tree Spanners of Homogeneously Orderable Graphs New Min-Max Theorems for Weakly Chordal and Dually Chordal Graphs Spanners for bounded tree-length graphs Diameters, Centers, and Approximating Trees of δ-Hyperbolic Geodesic Spaces and Graphs Additive Spanners for Circle Graphs and Polygonal Graphs How to Use Spanning Trees to Navigate in Graphs Navigating in a Graph by Aid of Its Spanning Tree Optimal Distance Labeling for Interval Graphs and Related Graph Families Approximation of minimum weight spanners for sparse graphs