{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:33Z","timestamp":1781345673265,"version":"3.54.1"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,3,1]],"date-time":"2009-03-01T00:00:00Z","timestamp":1235865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["829959"],"award-info":[{"award-number":["829959"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p>\n            We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) and an edge set\n            <jats:italic>E<\/jats:italic>\n            on\n            <jats:italic>V<\/jats:italic>\n            disjoint to\n            <jats:italic>E<\/jats:italic>\n            , find a minimum-size subset of edges\n            <jats:italic>F<\/jats:italic>\n            \u2286\n            <jats:italic>E<\/jats:italic>\n            such that (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            \u222a\n            <jats:italic>F<\/jats:italic>\n            ) is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + \u03b5 of Nagamochi.\n          <\/jats:p>","DOI":"10.1145\/1497290.1497297","type":"journal-article","created":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T16:34:22Z","timestamp":1239035662000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2"],"prefix":"10.1145","volume":"5","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jon","family":"Feldman","sequence":"additional","affiliation":[{"name":"Google, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[{"name":"Rutgers University, Camden, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zeev","family":"Nutov","sequence":"additional","affiliation":[{"name":"The Open University of Israel, Raanana, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,3,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 7th Annual European Symposium on Algorithms, 510--520","author":"Cheriyan J.","unstructured":"Cheriyan , J. , Jord\u00e1n , 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 . Cheriyan, J., Jord\u00e1n, 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."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205044"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization, 90--101","author":"Even G.","unstructured":"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 . 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."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90059-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 725--734","author":"Jothi R.","unstructured":"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 . 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."},{"key":"e_1_2_1_9_1","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"Khuller S.","unstructured":"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. 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."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1010"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Kortsarz G. and Nutov Z. 2007. Approximating minimum cost connectivity problems. In Handbook of Approximation Algorithms and Metahueristics T. F. Gonzales Ed. Chapman &amp; Hall\/CRC (Chapter 58).  Kortsarz G. and Nutov Z. 2007. Approximating minimum cost connectivity problems. In Handbook of Approximation Algorithms and Metahueristics T. F. Gonzales Ed. Chapman &amp; Hall\/CRC (Chapter 58).","DOI":"10.1201\/9781420010749.ch58"},{"key":"e_1_2_1_12_1","unstructured":"Maduel Y. and Nutov Z. 2008. Covering a laminar family by leaf to leaf links. Manuscript.  Maduel Y. and Nutov Z. 2008. Covering a laminar family by leaf to leaf links. Manuscript."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00218-4"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497290.1497297","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1497290.1497297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:40Z","timestamp":1750250740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497290.1497297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1145\/1497290.1497297"],"URL":"https:\/\/doi.org\/10.1145\/1497290.1497297","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3]]},"assertion":[{"value":"2006-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}