MISC

査読有り
2003年

Augmenting forests to meet odd diameter requirements

ALGORITHMS AND COMPUTATION, PROCEEDINGS
  • T Ishii
  • ,
  • S Yamamoto
  • ,
  • H Nagamochi

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.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000188242500045&DestApp=WOS_CPL
ID情報
  • ISSN : 0302-9743
  • Web of Science ID : WOS:000188242500045

エクスポート
BibTeX RIS