{"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":1781345675436,"version":"3.54.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,6,29]],"date-time":"2012-06-29T00:00:00Z","timestamp":1340928000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00453-012-9662-2","type":"journal-article","created":{"date-parts":[[2012,6,28]],"date-time":"2012-06-28T16:42:56Z","timestamp":1340901776000},"page":"287-311","source":"Crossref","is-referenced-by-count":22,"title":["Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs"],"prefix":"10.1007","volume":"68","author":[{"given":"Glencora","family":"Borradaile","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siamak","family":"Tazari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,6,29]]},"reference":[{"issue":"1","key":"9662_CR1","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Appl. Math. 23(1), 11\u201324 (1989)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"9662_CR2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s10107-003-0438-y","volume":"97","author":"S. Arora","year":"2003","unstructured":"Arora, S.: Approximation schemes for NP-hard geometric optimization problems: A\u00a0survey. Math. Program. 97(1\u20132), 43\u201369 (2003)","journal-title":"Math. Program."},{"issue":"1","key":"9662_CR3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"9662_CR4","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1137\/1.9781611973082.79","volume-title":"SODA\u201911: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms","author":"M. Bateni","year":"2011","unstructured":"Bateni, M., Chekuri, C., Ene, A., Hajiaghayi, M.T., Korula, N., Marx, D.: Prize-collecting Steiner problems on planar graphs. In: SODA\u201911: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 1028\u20131049. SIAM, Philadelphia (2011)"},{"key":"9662_CR5","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1145\/1806689.1806720","volume-title":"STOC\u201910: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing","author":"M. Bateni","year":"2010","unstructured":"Bateni, M., Hajiaghayi, M., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. In: STOC\u201910: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, pp. 211\u2013220. ACM, New York (2010)"},{"key":"9662_CR6","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/978-3-540-70575-8_40","volume-title":"ICALP\u201908: Proceedings of the 35th International Colloquium on Automata, Languages and Programming","author":"G. Borradaile","year":"2008","unstructured":"Borradaile, G., Klein, P.: The two-edge connectivity survivable network problem in planar graphs. In: ICALP\u201908: Proceedings of the 35th International Colloquium on Automata, Languages and Programming. LNCS, vol. 5125, pp. 485\u2013501. Springer, Berlin (2008)"},{"key":"9662_CR7","first-page":"1285","volume-title":"SODA\u201907: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"G. Borradaile","year":"2007","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: A polynomial-time approximation scheme for Steiner tree in planar graphs. In: SODA\u201907: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1285\u20131294 (2007)"},{"key":"9662_CR8","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/978-3-540-73951-7_25","volume-title":"WADS\u201907: Proceedings of the 10th Workshop on Algorithms and Data Structures","author":"G. Borradaile","year":"2007","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: Steiner tree in planar graphs: an O(nlogn) approximation scheme with singly exponential dependence on epsilon. In: WADS\u201907: Proceedings of the 10th Workshop on Algorithms and Data Structures. LNCS, vol. 4619, pp. 275\u2013286. Springer, Berlin (2007)"},{"key":"9662_CR9","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: An O(nlogn) approximation scheme for Steiner tree in planar graphs. ACM Trans. Algorithms 5(3) (2009)","DOI":"10.1145\/1541885.1541892"},{"key":"9662_CR10","first-page":"89","volume-title":"SODA\u201907: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"S. Cabello","year":"2007","unstructured":"Cabello, S., Chambers, E.W.: Multiple source shortest paths in a genus g graph. In: SODA\u201907: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 89\u201397. SIAM, Philadelphia (2007)"},{"key":"9662_CR11","series-title":"LNCS","first-page":"374","volume-title":"IWOCA\u201911: Revised Selected Papers of the 22nd International Workshop on Combinatorial Algorithms","author":"M. Chimani","year":"2011","unstructured":"Chimani, M., Mutzel, P., Zey, B.: Improved Steiner tree algorithms for bounded treewidth. In: IWOCA\u201911: Revised Selected Papers of the 22nd International Workshop on Combinatorial Algorithms. LNCS, vol. 7056, pp. 374\u2013386. Springer, Berlin (2011)"},{"issue":"6","key":"9662_CR12","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52(6), 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"9662_CR13","first-page":"590","volume-title":"SODA\u201905: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality: New connections between FPT algorithms and PTASs. In: SODA\u201905: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 590\u2013601 (2005)"},{"key":"9662_CR14","first-page":"441","volume-title":"STOC\u201911: Proceedings of the 43rd Symposium on Theory of Computing","author":"E.D. Demaine","year":"2011","unstructured":"Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.: Contraction decomposition in H-minor-free graphs and algorithmic applications. In: STOC\u201911: Proceedings of the 43rd Symposium on Theory of Computing, pp. 441\u2013450. ACM, New York (2011)"},{"key":"9662_CR15","first-page":"278","volume-title":"SODA\u201907: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"E.D. Demaine","year":"2007","unstructured":"Demaine, E.D., Hajiaghayi, M., Mohar, B.: Approximation algorithms via contraction decomposition. In: SODA\u201907: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 278\u2013287. SIAM, Philadelphia (2007)"},{"key":"9662_CR16","first-page":"599","volume-title":"SODA\u201903: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"D. Eppstein","year":"2003","unstructured":"Eppstein, D.: Dynamic generators of topologically embedded graphs. In: SODA\u201903: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 599\u2013608. SIAM, Philadelphia (2003)"},{"issue":"1","key":"9662_CR17","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","volume":"13","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Italiano, G., Tamassia, R., Tarjan, R., Westbrook, J., Yung, M.: Maintenance of a minimum spanning forest in a dynamic planar graph. J. Algorithms 13(1), 33\u201354 (1992). Special issue for 1st SODA","journal-title":"J. Algorithms"},{"key":"9662_CR18","first-page":"1038","volume-title":"SODA\u201905: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J. Erickson","year":"2005","unstructured":"Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: SODA\u201905: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1038\u20131046. SIAM, Philadelphia (2005)"},{"issue":"4","key":"9662_CR19","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1287\/moor.12.4.634","volume":"12","author":"R.E. Erickson","year":"1987","unstructured":"Erickson, R.E., Monma, C.L., Veinott, A.F.,\u00a0Jr.: Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12(4), 634\u2013664 (1987)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"9662_CR20","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/s00493-003-0037-9","volume":"23","author":"M. Grohe","year":"2003","unstructured":"Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23(4), 613\u2013632 (2003)","journal-title":"Combinatorica"},{"issue":"1","key":"9662_CR21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1), 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9662_CR22","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1145\/1132516.1132620","volume-title":"STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing","author":"P.N. Klein","year":"2006","unstructured":"Klein, P.N.: A subset spanner for planar graphs, with application to subset TSP. In: STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 749\u2013756 (2006)"},{"issue":"6","key":"9662_CR23","doi-asserted-by":"crossref","first-page":"1926","DOI":"10.1137\/060649562","volume":"37","author":"P.N. Klein","year":"2008","unstructured":"Klein, P.N.: A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput. 37(6), 1926\u20131952 (2008)","journal-title":"SIAM J. Comput."},{"key":"9662_CR24","unstructured":"Korach, E., Solel, N.: Linear time algorithm for minimum weight Steiner tree in graphs with bounded treewidth. Manuscript (1990)"},{"key":"9662_CR25","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K. Mehlhorn","year":"1988","unstructured":"Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett. 27, 125\u2013128 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9662_CR26","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1137\/S089548019529248X","volume":"12","author":"B. Mohar","year":"1999","unstructured":"Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math. 12(1), 6\u201326 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"9662_CR27","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. The John Hopkins University Press, Baltimore (2001)"},{"issue":"1","key":"9662_CR28","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N. Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.: Graph minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B 89(1), 43\u201376 (2003)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"3","key":"9662_CR29","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"9662_CR30","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1016\/j.dam.2008.08.002","volume":"157","author":"S. Tazari","year":"2009","unstructured":"Tazari, S., M\u00fcller-Hannemann, M.: Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation. Discrete Appl. Math. 157, 673\u2013684 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9662_CR31","unstructured":"Tazari, S., M\u00fcller-Hannemann, M.: Dealing with large hidden constants: Engineering a planar Steiner tree PTAS. ACM J. Exp. Algorithmics 16(3) (2011). Article 3.16. Special Issue on ALENEX\u201909"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9662-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9662-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9662-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T23:28:15Z","timestamp":1687562895000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9662-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,29]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9662"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9662-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6,29]]}}}