Abstract
Given a graph G=(V,E) and a positive integer D , we consider the problem of finding a minimum number of new edges E' such that the augmented graph G'=(V,E\cup E') is biconnected and has diameter no greater than D. In this note we show that this problem is NP-hard for all fixed D , by employing a reduction from the DOMINATING SET problem. We prove that the problem remains NP-hard even for forests and trees, but in this case we present approximation algorithms with worst-case bounds 3 (for even D ) and 6 (for odd D ). A closely related problem of finding a minimum number of edges such that the augmented graph has diameter no greater than D has been shown to be NP-hard by Schoone et al. [21] when D=3 , and by Li et al. [17] when D=2.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received April 19, 1999; revised June 5, 2001.
Rights and permissions
About this article
Cite this article
Chepoi, V., Vaxes, Y. Augmenting Trees to Meet Biconnectivity and Diameter Constraints. Algorithmica 33, 243–262 (2002). https://doi.org/10.1007/s00453-001-0113-8
Issue Date:
DOI: https://doi.org/10.1007/s00453-001-0113-8