Skip to main content
Springer Nature Link
Log in

An approximation algorithm for minimum-cost vertex-connectivity problems

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has certain vertex-connectivity properties. In the survivable network design problem, a valuer ij for each pair of verticesi andj is given, and a minimum-cost set of edges such that there arer ij vertex-disjoint paths between verticesi andj must be found. In the case for whichr ij ∈{0, 1, 2} for alli, j, we can find a solution of cost no more than three times the optimal cost in polynomial time. In the case in whichr ij =k for alli, j, we can find a solution of cost no more than 2H(k) times optimal, where\(\mathcal{H}(n) = 1 + \tfrac{1}{2} + \cdot \cdot \cdot + \tfrac{1}{n}\). No approximation algorithms were previously known for these problems. Our algorithms rely on a primal-dual approach which has recently led to approximation algorithms for many edge-connectivity problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. Agrawal, P. Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks.SIAM Journal on Computing, 24:440–456, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  2. K. P. Eswaran and R. E. Tarjan. Augmentation problems.SIAM Journal on Computing, 5:653–665, 1976.

    Article  MATH  MathSciNet  Google Scholar 

  3. M. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, E. Tardos, and D. Williamson. Improved approximation algorithms for network design problems. InProceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 223–232, 1994.

  4. M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems.SIAM Journal on Computing, 24:296–317, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  5. M. Grötschel, C. L. Monma, and M. Stoer. Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints.Operations Research, 40:309–330, 1992.

    MATH  MathSciNet  Google Scholar 

  6. F. Harary. The maximum connectivity of a graph.Proceedings of the National Academy of Sciences, USA, 48:1142–1146, 1962.

    Article  MATH  Google Scholar 

  7. T. Hsu. On four-connecting a triconnected graph. InProceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 70–79, 1992.

  8. T. Hsu and V. Ramachandran. A linear time algorithm for triconnectivity augmentation. InProceedings of the 32nd Annual Symposium on Foundations of Computer Science, pages 548–559, 1991.

  9. T. Jordán. On the optimal vertex-connectivity augmentation.Journal of Combinatorial Theory, Series B, 63:8–20, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  10. S. Khuller and B. Raghavachari. Improved approximation algorithms for uniform connectivity problems.Journal of Algorithms, 21:434–450, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  11. S. Khuller and R. Thurimella. Approximation algorithms for graph augmentation.Journal of Algorithms, 14:214–225, 1993.

    Article  MATH  MathSciNet  Google Scholar 

  12. P. Klein and R. Ravi. When cycles collapse: A general approximation technique for constrained two-connectivity problems. InProceedings of the Third MPS Conference on Integer Programming and Combinatorial Optimization, pages 39–55, 1993. Also appears as Technical Report CS-92-30, Brown University.

  13. K. Menger. Zur allgemeinen Kurventheorie.Fundamenta Mathematicae, 10:96–115, 1927.

    MATH  Google Scholar 

  14. M. Mihail, D. Shallcross, N. Dean, and M. Mostrel. A commercial application of survivable network design: ITP/INPLANS CCS Network Topology Analyzer. InProceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 279–287, 1996.

  15. C. L. Monma and D. F. Shallcross. Methods for designing communication networks with certain two-connected survivability constraintsOperations Research, pages 531–541, 1989.

  16. C. H. Papadimitriou and K. SteiglitzCombinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982.

    MATH  Google Scholar 

  17. M. Rauch. Improved data structures for fully dynamic biconnectivity. InProceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 686–695, 1994. Submitted toSIAM Journal on Computing.

  18. R Ravi and D. P. Williamson. An approximation algorithm for minimum-cost vertex-connectivity problems. InProceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 332–341, 1995.

  19. K. Steiglitz, P. Weiner, and D. Kleitman. The design of minimal cost survivable networksIEEE Transactions on Circuit Theory, 16:455–460, 1969.

    MathSciNet  Google Scholar 

  20. M. Stoer.Design of Survivable Networks. Lecture Notes in Mathematics, volume 1531. Springer-Verlag, Berlin, 1992.

    MATH  Google Scholar 

  21. T. Watanabe and A. Nakamura. A minimum 3-connectivity augmentation of a graph.Journal of Computer and System Sciences, 46:91–128, 1993.

    Article  MATH  MathSciNet  Google Scholar 

  22. D. P. Williamson. On the design of approximation algorithms for a class of graph problems. Ph.D. thesis, MIT, Cambridge, MA, September 1993. Also appears as Technical Report MIT/LCS/TR-584.

    Google Scholar 

  23. D. P. Williamson and M. X. Goemans. Computational experience with an approximation algorithm on large-scale Euclidean matching instances.INFORMS Journal on Computing, 8:29–40, 1996.

    Article  MATH  Google Scholar 

  24. D. P. Williamson., M. X. Goemans, M. Mihail, and V. V. Vazirani. A primal-dual approximation algorithm for generalized Steiner network problems.Combinatorica, 15:435–454, 1995.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Graduate School of Industrial Administration, Carnegie Mellon University, 15213, Pittsburgh, PA, USA

    R. Ravi

  2. IBM TJ Watson Research Center, Room 33-219, P.O. Box 218, 10598, Yorktown Heights, NY, USA

    D. P. Williamson

Authors
  1. R. Ravi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D. P. Williamson
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communciated by M. X. Goemans.

This research was supported by NSF Grant CCR-91-03937 and a DIMACS postdoctoral fellowship, and was conducted in part while the author was visiting MIT.

This research was supported by an NSF Graduate Fellowship and an NSF Postdoctoral Fellowship, and was conducted in part while the author was a graduate student at MIT and in part while a postdoc at Cornell.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ravi, R., Williamson, D.P. An approximation algorithm for minimum-cost vertex-connectivity problems. Algorithmica 18, 21–43 (1997). https://doi.org/10.1007/BF02523686

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02523686

Key Words

Search

Navigation