Augmenting forests to meet odd diameter requirements |
| |
Authors: | Toshimasa Ishii Shigeyuki Yamamoto Hiroshi Nagamochi |
| |
Institution: | aDepartment of Information and Computer Sciences, Toyohashi University of Technology, Aichi 441-8580, Japan;bI FOR COM Co., Ltd. Kanagawa 220-0207, Japan;cDepartment of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan |
| |
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(|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 the augmented graph is additionally required to be biconnected. |
| |
Keywords: | Undirected graph Graph augmentation problem Diameter Forest Approximation algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|