Augmenting Trees to Meet Biconnectivity and Diameter Constraints |
| |
Authors: | V Chepoi Y Vaxes |
| |
Affiliation: | (1) Laboratoire d'Informatique Fondamentale, Université de la Méditerranée, Faculté des Sciences de Luminy, F-13288 Marseille Cedex 9, France. {chepoi,vaxes}@lim.univ-mrs.fr., FR |
| |
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.
Received April 19, 1999; revised June 5, 2001. |
| |
Keywords: | , Biconnectivity augmentation, Diameter, Radius, Trees, Approximation algorithms, |
本文献已被 SpringerLink 等数据库收录! |
|