Name
Abstract | ||
|---|---|---|
Given a graph G = (V;E) and an integer D ‚ 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 ‚ 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(jV j3) 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 the augmented graph is additionally required to be biconnected. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.disopt.2005.10.006 | Discrete Optimization |
Keywords | DocType | Volume |
constant factor,odd diameter requirement,graph augmentation problem,constant factor approximation algorithm,constant approximation algorithm,arbitrary graph,forest,diameter,undirected graph,augmented graph,augmenting forest,graph g,odd d,approximation algorithm,augmenting g,forest g,integer d,linear time | Journal | 3 |
Issue | ISSN | Citations |
2 | Discrete Optimization | 9 |
PageRank | References | Authors |
0.95 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshimasa Ishii | 1 | 110 | 17.03 |
| Shigeyuki Yamamoto | 2 | 9 | 0.95 |
| Hiroshi Nagamochi | 3 | 1513 | 174.40 |