0
喜欢
0
书签
声明论文
Additive Spanners for k-Chordal Graphs   
摘  要:   In this paper we show that every chordal graph with n ver- tices and m edges admits an additive 4-spanner with at most 2n−2 edges and an additive 3-spanner with at most O(n · log n) edges. This signifi- cantly improves results of Peleg and Schaffer from (Graph Spanners, J. Graph Theory, 13(1989), 99-116). Our spanners are additive and easier to construct. An additive 4-spanner can be constructed in linear time while an additive 3-spanner is constructable in O(m · log n) time. Fur- thermore, our method can be extended to graphs with largest induced cycles of length k. Any such graph admits an additive (k + 1)-spanner with at most 2n − 2 edges which is constructable in O(n · k + m) time.
发  表:   Italian Conference on Algorithms and Complexity  2003

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

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

Feedback
Feedback
Feedback
我想反馈:
排行榜