{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:35Z","timestamp":1750220555684,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T00:00:00Z","timestamp":1619740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1016684 and CCF-1910149"],"award-info":[{"award-number":["CCF-1016684 and CCF-1910149"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>\n            We consider\n            <jats:italic>node-weighted<\/jats:italic>\n            survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) and integer connectivity requirements\n            <jats:italic>r<\/jats:italic>\n            (\n            <jats:italic>uv<\/jats:italic>\n            ) for each unordered pair of nodes\n            <jats:italic>uv<\/jats:italic>\n            . The goal is to find a minimum weighted subgraph\n            <jats:italic>H<\/jats:italic>\n            of\n            <jats:italic>G<\/jats:italic>\n            such that\n            <jats:italic>H<\/jats:italic>\n            contains\n            <jats:italic>r<\/jats:italic>\n            (\n            <jats:italic>uv<\/jats:italic>\n            ) disjoint paths between\n            <jats:italic>u<\/jats:italic>\n            and\n            <jats:italic>v<\/jats:italic>\n            for each node pair\n            <jats:italic>uv<\/jats:italic>\n            . Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here,\n            <jats:italic>k<\/jats:italic>\n            = max\u2009\n            <jats:sup>\n              <jats:italic>uv<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>r<\/jats:italic>\n            (\n            <jats:italic>uv<\/jats:italic>\n            ) is the maximum connectivity requirement. This improves upon the\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            log\u2009\n            <jats:italic>n<\/jats:italic>\n            )-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an\n            <jats:italic>O<\/jats:italic>\n            (1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm.\n          <\/jats:p>","DOI":"10.1145\/3447959","type":"journal-article","created":{"date-parts":[[2021,6,6]],"date-time":"2021-06-06T09:50:24Z","timestamp":1622973024000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Node-weighted Network Design in Planar and Minor-closed Families of Graphs"],"prefix":"10.1145","volume":"17","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[{"name":"University of Illinois, IL"}]},{"given":"Alina","family":"Ene","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}]},{"given":"Ali","family":"Vakilian","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago (TTIC), Chicago, IL"}]}],"member":"320","published-online":{"date-parts":[[2021,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"M. Bateni M. Hajiaghayi and V. Liaghat. 2013. Improved approximation algorithms for (budgeted) node-weighted Steiner problems. In International Colloquium on Automata Languages and Programming. Springer 81\u201392.  M. Bateni M. Hajiaghayi and V. Liaghat. 2013. Improved approximation algorithms for (budgeted) node-weighted Steiner problems. In International Colloquium on Automata Languages and Programming. Springer 81\u201392.","DOI":"10.1007\/978-3-642-39206-1_8"},{"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":"crossref","unstructured":"P. Berman and G. Yaroslavtsev. 2012. Primal-dual approximation algorithms for node-weighted network design in planar graphs. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer 50\u201360.  P. Berman and G. Yaroslavtsev. 2012. Primal-dual approximation algorithms for node-weighted network design in planar graphs. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer 50\u201360.","DOI":"10.1007\/978-3-642-32512-0_5"},{"key":"e_1_2_1_5_1","first-page":"3","article-title":"An O(N Log N) approximation scheme for Steiner tree in planar graphs","volume":"5","author":"Borradaile G.","year":"2009","unstructured":"G. Borradaile , P. Klein , and C. Mathieu . 2009 . An O(N Log N) approximation scheme for Steiner tree in planar graphs . ACM Trans. Algor. 5 , 3 (July 2009). DOI:https:\/\/doi.org\/10.1145\/1541885.1541892 10.1145\/1541885.1541892 G. Borradaile, P. Klein, and C. Mathieu. 2009. An O(N Log N) approximation scheme for Steiner tree in planar graphs. ACM Trans. Algor. 5, 3 (July 2009). DOI:https:\/\/doi.org\/10.1145\/1541885.1541892","journal-title":"ACM Trans. Algor."},{"volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing. ACM, 583\u2013592","author":"Byrka J.","key":"e_1_2_1_6_1","unstructured":"J. Byrka , F. Grandoni , T. Rothvo\u00df , and L. Sanit\u00e0 . 2010. An improved LP-based approximation for Steiner tree . In Proceedings of the 42nd ACM Symposium on Theory of Computing. ACM, 583\u2013592 . J. Byrka, F. Grandoni, T. Rothvo\u00df, and L. Sanit\u00e0. 2010. An improved LP-based approximation for Steiner tree. In Proceedings of the 42nd ACM Symposium on Theory of Computing. ACM, 583\u2013592."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"C. Chekuri A. Ene and A. Vakilian. 2012. Node-weighted network design in planar and minor-closed families of graphs. In Automata Languages and Programming. Springer 206\u2013217.  C. Chekuri A. Ene and A. Vakilian. 2012. Node-weighted network design in planar and minor-closed families of graphs. In Automata Languages and Programming. Springer 206\u2013217.","DOI":"10.1007\/978-3-642-31594-7_18"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"C. Chekuri A. Ene and A. Vakilian. 2012. Prize-collecting survivable network design in node-weighted graphs. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer 98\u2013109.  C. Chekuri A. Ene and A. Vakilian. 2012. Prize-collecting survivable network design in node-weighted graphs. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer 98\u2013109.","DOI":"10.1007\/978-3-642-32512-0_9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0016-z"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a018"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897635"},{"key":"e_1_2_1_13_1","first-page":"13","article-title":"Node-weighted Steiner tree and group Steiner tree in planar graphs","volume":"10","author":"Demaine E. D.","year":"2014","unstructured":"E. D. Demaine , M. Hajiaghayi , and P. N. Klein . 2014 . Node-weighted Steiner tree and group Steiner tree in planar graphs . ACM Trans. Algor. 10 , 3 (2014), 13 . E. D. Demaine, M. Hajiaghayi, and P. N. Klein. 2014. Node-weighted Steiner tree and group Steiner tree in planar graphs. ACM Trans. Algor. 10, 3 (2014), 13.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_14_1","unstructured":"A. Ene N. Korula and A. Vakilian. 2013. Connected domatic packings in node-capacitated graphs. CoRR abs\/1305.4308 (2013).  A. Ene N. Korula and A. Vakilian. 2013. Connected domatic packings in node-capacitated graphs. CoRR abs\/1305.4308 (2013)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.006"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.141"},{"key":"e_1_2_1_17_1","first-page":"49","article-title":"Spider covers for prize-collecting network activation problem","volume":"13","author":"Fukunaga T.","year":"2017","unstructured":"T. Fukunaga . 2017 . Spider covers for prize-collecting network activation problem . ACM Trans. Algor. 13 , 4 (2017), 49 . T. Fukunaga. 2017. Spider covers for prize-collecting network activation problem. ACM Trans. Algor. 13, 4 (2017), 49.","journal-title":"ACM Trans. Algor."},{"volume-title":"Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms. 223\u2013232","author":"Goemans M. X.","key":"e_1_2_1_18_1","unstructured":"M. X. Goemans , A. V. Goldberg , S. Plotkin , D. B. Shmoys , E. Tardos , and D. P. Williamson . 1994. Improved approximation algorithms for network design problems . In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms. 223\u2013232 . M. X. Goemans, A. V. Goldberg, S. Plotkin, D. B. Shmoys, E. Tardos, and D. P. Williamson. 1994. Improved approximation algorithms for network design problems. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms. 223\u2013232."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_20_1","unstructured":"M. X. Goemans and D. P. Williamson. 1997. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms for NP-hard Problems. PWS Publishing Co. 144\u2013191.  M. X. Goemans and D. P. Williamson. 1997. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms for NP-hard Problems. PWS Publishing Co. 144\u2013191."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009810"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2754"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sorms.2010.06.001"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00222-5"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1029"},{"volume-title":"Proceedings of the Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik.","author":"Kortsarz G.","key":"e_1_2_1_27_1","unstructured":"G. Kortsarz and Z. Nutov . 2010. Approximating minimum cost connectivity problems . In Proceedings of the Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. G. Kortsarz and Z. Nutov. 2010. Approximating minimum cost connectivity problems. In Proceedings of the Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579141"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9869-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.017"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/080729645"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390176.2390177"},{"key":"e_1_2_1_33_1","volume-title":"Proc. of LATIN.","author":"Nutov Z.","year":"2012","unstructured":"Z. Nutov . 2012 . Approximating Steiner network activation problems . In Proc. of LATIN. Z. Nutov. 2012. Approximating Steiner network activation problems. In Proc. of LATIN."},{"key":"e_1_2_1_34_1","first-page":"3","article-title":"Erratum: Approximating minimum-cost connectivity problems via uncrossable bifamilies","volume":"14","author":"Nutov Z.","year":"2018","unstructured":"Z. Nutov . 2018 . Erratum: Approximating minimum-cost connectivity problems via uncrossable bifamilies . ACM Trans. Algor. 14 , 3 (June 2018). DOI:https:\/\/doi.org\/10.1145\/3186991 10.1145\/3186991 Z. Nutov. 2018. Erratum: Approximating minimum-cost connectivity problems via uncrossable bifamilies. ACM Trans. Algor. 14, 3 (June 2018). DOI:https:\/\/doi.org\/10.1145\/3186991","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.78"},{"volume-title":"Node-weighted Prize-collecting Survivable Network Design Problems. Master\u2019s thesis","author":"Vakilian A.","key":"e_1_2_1_36_1","unstructured":"A. Vakilian . 2013. Node-weighted Prize-collecting Survivable Network Design Problems. Master\u2019s thesis . University of Illinois , Urbana-Champaign, IL. A. Vakilian. 2013. Node-weighted Prize-collecting Survivable Network Design Problems. Master\u2019s thesis. University of Illinois, Urbana-Champaign, IL."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01299747"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447959","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447959","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447959","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:24Z","timestamp":1750195704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447959"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,30]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3447959"],"URL":"https:\/\/doi.org\/10.1145\/3447959","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2021,4,30]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}