Collective additive tree spanners for circle graphs and polygonal graphs

详细信息    查看全文

• 作者：Feodor F. Dragan^a ; ^{dragan@cs.kent.edu} ; Derek G. Corneil^b ; ^{dgc@cs.toronto.edu} ; Ekkehard Kö ; hler^c ; ^{ekoehler@math.TU-Cottbus.DE} ; Yang Xiang^d ; ^{yxiang@bmi.osu.edu}
• 关键词：Graph algorithms ; Collective additive tree spanners ; Circle graphs ; Polygonal graphs ; Balanced separators
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 出版时间：August, 2012
• 年：2012
• 卷：160
• 期：12
• 页码：1717-1729
• 全文大小：383 K

文摘

A graph is said to admit a system of collective additive tree -spanners if there is a system of at most spanning trees of such that for any two vertices of a spanning tree exists such that the distance in between and is at most plus their distance in . In this paper, we examine the problem of finding ¡°small?systems of collective additive tree -spanners for small values of on circle graphs and on polygonal graphs. Among other results, we show that every -vertex circle graph admits a system of at most collective additive tree 2-spanners and every -vertex -polygonal graph admits a system of at most collective additive tree 2-spanners. Moreover, we show that every -vertex -polygonal graph admits an additive -spanner with at most edges and every -vertex 3-polygonal graph admits a system of at most three collective additive tree 2-spanners and an additive tree 6-spanner. All our collective tree spanners as well as all sparse spanners are constructible in polynomial time.