When Cycles Collapse: A General Approximation Technique for Constrained Two-Connectivity Problems
R. Ravi, Philip N. Klein · 1992
We present a general approximation technique for a class of network design problems where we seek a network of minimum cost that satisfies certain communication requirements and is resilient to worst-case single-link failures. Our algorithm runs in O(n² log n) time on a graph with n nodes and outputs a solution of cost at most thrice the optimum. We extend our technique to obtain approximation algorithms for augmenting a given network so as to satisfy certain communication requirements and achieve resilience to single-link failures. Our technique allows one to find nearly minimum-cost two-connected networks for a variety of connectivity requirements. For example, our result generalizes earlier results on finding a minimumcost two-connected subgraph of a given edge-weighted graph in [3, 9] and an earlier result on finding a minimum-cost subgraph two-connecting a specified subset of the nodes in [14]. Using our technique, we can also approximately solve for the first time a ...