An approach to robust network construction from graph augmentation problems
Takuo Watanabe, Y. Higashi, Akira Nakamura · 2002
The problem of constructing a robust communication network by adding a minimum-cost set of new links is discussed. The problem is formulated as the k-edge-connectivity (k-vertex-connectivity, respectively) augmentation problem for a specified set of vertices. For k=2, an O( mod V mod /sup 2/) (O mod V mod /sup 3/) approximation algorithm is proposed, with the worst approximation no greater than twice (less than four times) the optimal.>