0
喜欢
0
书签
声明论文
Collective Tree Spanners and Routing in AT-free Related Graphs   
摘  要:   In this paper we study collective additive tree spanners for families of graphs that either contain or are contained in AT-free graphs. We say that a graph G = (V,E) admits a system of µ collective 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 2 T (G) exists such that dT(x,y) � dG(x,y) + r. Among other results, we show that AT-free graphs have a system of two collective additive tree 2-spanners (whereas there are trapezoid graphs that do not admit any additive tree 2-spanner). Furthermore, based on this collection, we derive a compact and efficient routing scheme. Also, any DSP-graph (there exists a dominating shortest path) admits an additive tree 4-spanner, a system of two collective additive tree 3-spanners and a system of five collective additive tree 2-spanners.
发  表:   Workshop on Graph-Theoretic Concepts in Computer Science  2004

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

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

Feedback
Feedback
Feedback
我想反馈:
排行榜