{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:35Z","timestamp":1781345675425,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,19]],"date-time":"2016-06-19T00:00:00Z","timestamp":1466294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897635","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T13:04:07Z","timestamp":1465563847000},"page":"584-597","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximating connectivity domination in weighted bounded-genus graphs"],"prefix":"10.1145","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"ENS, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00c9ric","family":"Colin de Verdi\u00e8re","sequence":"additional","affiliation":[{"name":"CNRS, France \/ ENS, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philip N.","family":"Klein","sequence":"additional","affiliation":[{"name":"Brown University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[{"name":"CNRS, France \/ ENS, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Meierfrankenfeld","sequence":"additional","affiliation":[{"name":"Brown University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90072-H"},{"key":"e_1_3_2_1_2_1","first-page":"41","volume-title":"ACM-SIAM Symp. on Discrete Algorithms","author":"Arora S.","year":"1998","unstructured":"S. Arora , M. Grigni , D. R. Karger , P. N. Klein , and A. Woloszyn . A polynomial-time approximation scheme for weighted planar graph TSP . In ACM-SIAM Symp. on Discrete Algorithms , pages 33\u2013 41 , 1998 . S. Arora, M. Grigni, D. R. Karger, P. N. Klein, and A. Woloszyn. A polynomial-time approximation scheme for weighted planar graph TSP. In ACM-SIAM Symp. on Discrete Algorithms, pages 33\u201341, 1998."},{"key":"e_1_3_2_1_3_1","first-page":"151","volume-title":"Algorithms and Computations","author":"Bafna V.","unstructured":"V. Bafna , P. Berman , and T. Fujito . Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs . In Algorithms and Computations , pages 142\u2013 151 . Springer, 1995. V. Bafna, P. Berman, and T. Fujito. Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In Algorithms and Computations, pages 142\u2013151. Springer, 1995."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305109"},{"key":"e_1_3_2_1_6_1","first-page":"60","volume-title":"Alg. and Tech.","author":"Berman P.","unstructured":"P. Berman and G. Yaroslavtsev . Primal-dual approximation algorithms for node-weighted network design in planar graphs. In Approximation, Randomization, and Combinatorial Optimization . Alg. and Tech. , pages 50\u2013 60 . Springer, 2012. P. Berman and G. Yaroslavtsev. Primal-dual approximation algorithms for node-weighted network design in planar graphs. In Approximation, Randomization, and Combinatorial Optimization. Alg. and Tech., pages 50\u201360. Springer, 2012."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13182-0_31"},{"key":"e_1_3_2_1_8_1","first-page":"590","volume-title":"WADS","author":"Bodlaender H. L.","year":"1989","unstructured":"H. L. Bodlaender . On linear time minor tests and depth first search. In W. on Algorithms and Data Structures , WADS , pages 577\u2013 590 , 1989 . H. L. Bodlaender. On linear time minor tests and depth first search. In W. on Algorithms and Data Structures, WADS, pages 577\u2013590, 1989."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9056-z"},{"key":"e_1_3_2_1_10_1","first-page":"637","volume-title":"Languages and Programming","author":"Bodlaender H. L.","unstructured":"H. L. Bodlaender and D. M. Thilikos . Constructive linear time algorithms for branchwidth. In Automata , Languages and Programming , pages 627\u2013 637 . Springer, 1997. H. L. Bodlaender and D. M. Thilikos. Constructive linear time algorithms for branchwidth. In Automata, Languages and Programming, pages 627\u2013637. Springer, 1997."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.12.002"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.10.010"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.27"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10097"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_3_2_1_17_1","first-page":"601","volume-title":"ACM-SIAM Symp. on Discrete Algorithms","author":"Demaine E. D.","year":"2005","unstructured":"E. D. Demaine and M. Hajiaghayi . Bidimensionality: new connections between FPT algorithms and PTASs . In ACM-SIAM Symp. on Discrete Algorithms , pages 590\u2013 601 , 2005 . E. D. Demaine and M. Hajiaghayi. Bidimensionality: new connections between FPT algorithms and PTASs. In ACM-SIAM Symp. on Discrete Algorithms, pages 590\u2013601, 2005."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601070"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9296-1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90130-8"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_3_2_1_23_1","first-page":"608","volume-title":"ACM-SIAM Symp. on Discrete Algorithms","author":"Eppstein D.","year":"2003","unstructured":"D. Eppstein . Dynamic generators of topologically embedded graphs . In ACM-SIAM Symp. on Discrete Algorithms , pages 599\u2013 608 , 2003 . D. Eppstein. Dynamic generators of topologically embedded graphs. In ACM-SIAM Symp. on Discrete Algorithms, pages 599\u2013608, 2003."},{"key":"e_1_3_2_1_24_1","volume-title":"Graph separators","author":"Erickson J.","year":"2009","unstructured":"J. Erickson . Graph separators , 2009 . Available at jeffe.cs.illinois.edu\/teaching\/comptop\/2009\/ notes\/separators.pdf. J. Erickson. Graph separators, 2009. Available at jeffe.cs.illinois.edu\/teaching\/comptop\/2009\/ notes\/separators.pdf."},{"key":"e_1_3_2_1_25_1","first-page":"1046","volume-title":"ACM-SIAM Symp. on Discrete Algorithms","author":"Erickson J.","year":"2005","unstructured":"J. Erickson and K. Whittlesey . Greedy optimal homotopy and homology generators . In ACM-SIAM Symp. on Discrete Algorithms , pages 1038\u2013 1046 , 2005 . J. Erickson and K. Whittlesey. Greedy optimal homotopy and homology generators. In ACM-SIAM Symp. on Discrete Algorithms, pages 1038\u20131046, 2005."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00138-7"},{"key":"e_1_3_2_1_28_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman & amp; Co., 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009810"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796249"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009201"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2754"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1309-3"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_3_2_1_35_1","volume-title":"Complexity of Computer Comput","author":"Karp R.","year":"1972","unstructured":"R. Karp . Complexity of Computer Comput ., chapter Reducibility Among Combinatorial Problems. Plenum Press , 1972 . R. Karp. Complexity of Computer Comput., chapter Reducibility Among Combinatorial Problems. Plenum Press, 1972."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.7"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649562"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488672"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702963"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02017-9_31"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0944"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90030-9"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9089-3"},{"key":"e_1_3_2_1_46_1","volume-title":"Approximation algorithms for metric tree cover and generalized tour and tree covers. RAIRO - Operations Research, 41(3):305\u2013315","author":"Nguyen V. H.","year":"2007","unstructured":"V. H. Nguyen . Approximation algorithms for metric tree cover and generalized tour and tree covers. RAIRO - Operations Research, 41(3):305\u2013315 , 2007 . V. H. Nguyen. Approximation algorithms for metric tree cover and generalized tour and tree covers. RAIRO - Operations Research, 41(3):305\u2013315, 2007."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/850957.854188"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159898"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1007"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556952"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90022-9"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/313239.313261"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.035"}],"event":{"name":"STOC '16: Symposium on Theory of Computing","location":"Cambridge MA USA","acronym":"STOC '16","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897635","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:55:57Z","timestamp":1750222557000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":55,"alternative-id":["10.1145\/2897518.2897635","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897635","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}