skip to main content
research-article

A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

Published: 23 March 2009 Publication History

Abstract

We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph G = (V, E) and an edge set E on V disjoint to E, find a minimum-size subset of edges FE such that (V, EF) is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + ε of Nagamochi.

References

[1]
Cheriyan, J., Jordán, T., and Ravi, R. 1999. On 2-coverings and 2-packing of laminar families. In Proceedings of the 7th Annual European Symposium on Algorithms, 510--520.
[2]
Eswaran, K. P. and Tarjan, R. E. 1976. Augmentation problems. SIAM J. Comput. 5, 653--665.
[3]
Even, G., Feldman, J., Kortsarz, G., and Nutov, Z. 2001. A 3/2-approximation for augmenting a connected graph into a two-connected graph. In Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization, 90--101.
[4]
Frederickson, G. N. and Jájá, J. 1981. Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10, 270--283.
[5]
Frederickson, G. N. and Jájá, J. 1982. On the relationship between the biconnectivity augmentation and traveling salesman problem. Theor. Comput. Sci. 19, 2, 189--201.
[6]
Goemans, M. X. and Williamson, D. P. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296--317.
[7]
Jain, K. 2001. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica 21, 1, 39--60.
[8]
Jothi, R., Raghavachari, B., and Varadarajan, S. 2003. A 5/4-approximation algorithm for minimum 2-edge-connectivity. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 725--734.
[9]
Khuller, S. 1996. Approximation algorithms for finding highly connected subgraphs (chapter 6). In Approximation Algorithms for NP-Hard Problems, D. S. Hochbaum Ed. PWS Publishing, Boston, MA.
[10]
Khuller, S. and Thurimella, R. 1993. Approximation algorithms for graph augmentation. J. Algor. 14, 214--225.
[11]
Kortsarz, G. and Nutov, Z. 2007. Approximating minimum cost connectivity problems. In Handbook of Approximation Algorithms and Metahueristics, T. F. Gonzales, Ed. Chapman & Hall/CRC (Chapter 58).
[12]
Maduel, Y. and Nutov, Z. 2008. Covering a laminar family by leaf to leaf links. Manuscript.
[13]
Nagamochi, H. 2003. An approximation for finding a smallest 2-edge connected subgraph containing a specified spanning tree. Discrete Appl. Math. 126, 83--113.

Cited By

View all

Index Terms

  1. A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Algorithms
    ACM Transactions on Algorithms  Volume 5, Issue 2
    March 2009
    235 pages
    ISSN:1549-6325
    EISSN:1549-6333
    DOI:10.1145/1497290
    Issue’s Table of Contents
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 23 March 2009
    Accepted: 01 October 2008
    Revised: 01 October 2008
    Received: 01 October 2006
    Published in TALG Volume 5, Issue 2

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Approximation algorithms
    2. connectivity
    3. graphs

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Funding Sources

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)6
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 30 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)2-node-connectivity network designTheoretical Computer Science10.1016/j.tcs.2023.114367987(114367)Online publication date: Mar-2024
    • (2024)Better-than--approximations for leaf-to-leaf tree and connectivity augmentationMathematical Programming: Series A and B10.1007/s10107-023-02018-3207:1-2(515-549)Online publication date: 1-Sep-2024
    • (2024)Approximation algorithms for node and element connectivity augmentation problemsTheory of Computing Systems10.1007/s00224-024-10175-x68:5(1468-1485)Online publication date: 2-Oct-2024
    • (2023)A (1.5+ε)-Approximation Algorithm for Weighted Connectivity AugmentationProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585122(1820-1833)Online publication date: 2-Jun-2023
    • (2023)An Improved Approximation Algorithm for the Matching Augmentation ProblemSIAM Journal on Discrete Mathematics10.1137/21M145350537:1(163-190)Online publication date: 20-Jan-2023
    • (2023)Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger ApproachesSIAM Journal on Computing10.1137/21M1430601(STOC21-26-STOC21-103)Online publication date: 12-Apr-2023
    • (2023)Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner TreeSIAM Journal on Computing10.1137/21M142114352:3(718-739)Online publication date: 23-May-2023
    • (2022)Breaching the 2-approximation barrier for the forest augmentation problemProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520035(1598-1611)Online publication date: 9-Jun-2022
    • (2022)A Better-Than-2 Approximation for Weighted Tree Augmentation2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00010(1-12)Online publication date: Feb-2022
    • (2022)Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problemOperations Research Letters10.1016/j.orl.2022.10.00750:6(693-698)Online publication date: Nov-2022
    • Show More Cited By

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media