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.
发  表:   Siam Journal on Discrete Mathematics  2006

论文统计图
共享有10个版本
 [展开全部版本] 

Bibtex
创新指数 
阅读指数 
重现指数 
论文点评
还没有人点评哦

Feedback
Feedback
Feedback
我想反馈:
排行榜