2003年
Augmenting forests to meet odd diameter requirements
ALGORITHMS AND COMPUTATION, PROCEEDINGS
- ,
- ,
- 巻
- 2906
- 号
- 開始ページ
- 434
- 終了ページ
- 443
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
Given a graph G = (V, E), and an integer D greater than or equal to 1, we consider the problem of augmenting G by the smallest number of new edges so that the diameter becomes at most D. It is known that no constant approximation algorithms to this problem with an arbitrary graph G can be obtained unless P = NP.. For a forest G and an odd D greater than or equal to 3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest. G and an odd D; our algorithm delivers an 8-approximate; solution in O(\V\(3)) time. We also show that a 4-approximate solution to the problem with a forest G and an odd D can be obtained in linear time if an augmented graph is additionally required to be biconnected.
- リンク情報
- ID情報
-
- ISSN : 0302-9743
- Web of Science ID : WOS:000188242500045