{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:34Z","timestamp":1781345674503,"version":"3.54.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,4,25]],"date-time":"2017-04-25T00:00:00Z","timestamp":1493078400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["postdoctoral fellowship"],"award-info":[{"award-number":["postdoctoral fellowship"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-09-64037, CCF-14-09520,CCF-0963921"],"award-info":[{"award-number":["CCF-09-64037, CCF-14-09520,CCF-0963921"]}],"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":[[2016,6,15]]},"abstract":"<jats:p>\n                    Consider the following problem: given a graph with edge costs and a subset\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every pair of vertices in\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    . The problem is a failure-resilient analog of the Steiner tree problem arising, for example, in telecommunications applications. We study a more general mixed-connectivity formulation, also employed in telecommunications optimization. Given a number (or\n                    <jats:italic toggle=\"yes\">requirement<\/jats:italic>\n                    )\n                    <jats:italic toggle=\"yes\">r<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    ) \u2208 {0, 1, 2} for each vertex\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    in the graph, find a minimum-cost subgraph in which there are min {\n                    <jats:italic toggle=\"yes\">r<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">u<\/jats:italic>\n                    ),\n                    <jats:italic toggle=\"yes\">r<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    )} edge-disjoint\n                    <jats:italic toggle=\"yes\">u<\/jats:italic>\n                    -to-\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    paths for every pair\n                    <jats:italic toggle=\"yes\">u<\/jats:italic>\n                    ,\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    of vertices.\n                  <\/jats:p>\n                  <jats:p>\n                    We address the problem in planar graphs, considering a popular relaxation in which the solution is allowed to use multiple copies of the input-graph edges (paying separately for each copy). The problem is max SNP-hard in general graphs and strongly NP-hard in planar graphs. We give the first polynomial-time approximation scheme in planar graphs. The running time is\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ).\n                  <\/jats:p>\n                  <jats:p>Under the additional restriction that the requirements are only non-zero for vertices on the boundary of a single face of a planar graph, we give a polynomial-time algorithm to find the optimal solution.<\/jats:p>","DOI":"10.1145\/2831235","type":"journal-article","created":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T15:51:13Z","timestamp":1461599473000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs"],"prefix":"10.1145","volume":"12","author":[{"given":"Glencora","family":"Borradaile","sequence":"first","affiliation":[{"name":"Oregon State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philip","family":"Klein","sequence":"additional","affiliation":[{"name":"Brown University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,4,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133115"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_43"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_10"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","unstructured":"G. Borradaile E. Demaine and S. Tazari. 2012. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica (2012). DOI:http:\/\/dx.doi.org\/10.1016\/j.jda.2012.04.011 Online.","DOI":"10.1016\/j.jda.2012.04.011"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283521"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394893.2394928"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/314500.314573"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.4.634"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205044"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/314464.314497"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195092"},{"key":"e_1_2_1_16_1","volume-title":"A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica","author":"Jain K.","year":"2001","unstructured":"K. Jain. 2001. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 2001, 1 (21), 39--60."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/174652.174654"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132620"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649562"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 3rd International Conference on Integer Programming and Combinatorial Optimization. 39--55","author":"Klein P.","unstructured":"P. Klein and R. Ravi. 1993. When cycles collapse: A general approximation technique for constrained two-connectivity problems. In Proceedings of the 3rd International Conference on Integer Programming and Combinatorial Optimization. 39--55."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90066-X"},{"key":"e_1_2_1_22_1","volume-title":"Technical Report NII-2003-005E. National Institute of Informatics.","author":"Nakano S.","year":"2003","unstructured":"S. Nakano and T. Uno. 2003. Efficient Generation of Rooted Trees. Technical Report NII-2003-005E. National Institute of Informatics."},{"key":"e_1_2_1_23_1","unstructured":"R. Ravi. 1992. Approximation Algorithms for Steiner Augmentations for Two-Connectivity. Technical Report TR-CS-92-21. Brown University."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"M. Resende and P. Pardalos (Eds.). 2006. Handbook of Optimization in Telecommunications. Springer.","DOI":"10.1007\/978-0-387-30165-5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1932-1501641-2"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/647667.730970"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167268"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289500"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2831235","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2831235","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2831235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:24:03Z","timestamp":1763457843000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2831235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,25]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2831235"],"URL":"https:\/\/doi.org\/10.1145\/2831235","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,25]]},"assertion":[{"value":"2013-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}