{"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":1781345675806,"version":"3.54.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2011,10,1]],"date-time":"2011-10-01T00:00:00Z","timestamp":1317427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF 0832797"],"award-info":[{"award-number":["CCF 0832797"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0237113"],"award-info":[{"award-number":["CCF-0237113"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0205594CCF-0426582"],"award-info":[{"award-number":["CCF-0205594CCF-0426582"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["OTKA 67651"],"award-info":[{"award-number":["OTKA 67651"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1053605"],"award-info":[{"award-number":["1053605"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["528414"],"award-info":[{"award-number":["528414"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["832797"],"award-info":[{"award-number":["832797"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,10]]},"abstract":"<jats:p>\n            We give the first\n            <jats:italic>polynomial-time approximation scheme<\/jats:italic>\n            (PTAS) for the\n            <jats:italic>Steiner forest<\/jats:italic>\n            problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a\n            <jats:italic>Steiner forest spanner<\/jats:italic>\n            for such graphs. The crux of the process is a clustering procedure called\n            <jats:italic>prize-collecting clustering<\/jats:italic>\n            that breaks down the input instance into separate subinstances which are easier to handle; moreover, the terminals in different subinstances are far from each other. Each subinstance has a relatively inexpensive Steiner tree connecting all its terminals, and the subinstances can be solved (almost) separately. Another building block is a PTAS for\n            <jats:italic>Steiner forest<\/jats:italic>\n            on graphs of bounded treewidth. Surprisingly,\n            <jats:italic>Steiner forest<\/jats:italic>\n            is NP-hard even on graphs of treewidth 3. Therefore, our PTAS for bounded-treewidth graphs needs a nontrivial combination of approximation arguments and dynamic programming on the tree decomposition. We further show that\n            <jats:italic>Steiner forest<\/jats:italic>\n            can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a novel combination of dynamic programming and minimum cut computations, completing our thorough complexity study of\n            <jats:italic>Steiner forest<\/jats:italic>\n            in the range of bounded-treewidth graphs, planar graphs, and bounded-genus graphs.\n          <\/jats:p>","DOI":"10.1145\/2027216.2027219","type":"journal-article","created":{"date-parts":[[2011,10,27]],"date-time":"2011-10-27T13:17:37Z","timestamp":1319721457000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth"],"prefix":"10.1145","volume":"58","author":[{"given":"Mohammadhossein","family":"Bateni","sequence":"first","affiliation":[{"name":"Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammadtaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"University of Maryland at College Park"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,10]]},"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":"publisher","DOI":"10.1145\/103418.103437"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.39"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875526"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM","author":"Bateni M.","unstructured":"Bateni , M. , Chekuri , C. , Ene , A. , Hajiaghayi , M. , Korula , N. , and Marx , D . 2011. Prize-collecting Steiner problems on planar graphs . In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM , Philadelphia, PA, 1028--1049. Bateni, M., Chekuri, C., Ene, A., Hajiaghayi, M., Korula, N., and Marx, D. 2011. Prize-collecting Steiner problems on planar graphs. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 1028--1049."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Bateni M.","unstructured":"Bateni , M. , Hajiaghayi , M. , Klein , P. N. , and Mathieu , C . 2012. A polynomial-time approximation scheme for planar multiway cut . In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Bateni, M., Hajiaghayi, M., Klein, P. N., and Mathieu, C. 2012. A polynomial-time approximation scheme for planar multiway cut. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM","author":"Berman P.","unstructured":"Berman , P. and Ramaiyer , V . 1992. Improved approximations for the Steiner tree problem . In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM , Philadelphia, PA, 325--334. Berman, P. and Ramaiyer, V. 1992. Improved approximations for the Steiner tree problem. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 325--334."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.59"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS). Springer","author":"Borradaile G.","unstructured":"Borradaile , G. , Demaine , E. D. , and Tazari , S . 2009a. Polynomial-time approximation schemes for subset-connectivity problems in bounded genus graphs . In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS). Springer , Berlin, 171--182. Borradaile, G., Demaine, E. D., and Tazari, S. 2009a. Polynomial-time approximation schemes for subset-connectivity problems in bounded genus graphs. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS). Springer, Berlin, 171--182."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM","author":"Borradaile G.","unstructured":"Borradaile , G. , Mathieu , C. , and Klein , P. N . 2007. A polynomial-time approximation scheme for Steiner tree in planar graphs . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM , Philadelphia, PA, 1285--1294. Borradaile, G., Mathieu, C., and Klein, P. N. 2007. A polynomial-time approximation scheme for Steiner tree in planar graphs. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 1285--1294."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806769"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM","author":"Cabello S.","unstructured":"Cabello , S. and Chambers , E. W . 2007. Multiple source shortest paths in a genus g graph . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM , Philadelphia, PA, 89--97. Cabello, S. and Chambers, E. W. 2007. Multiple source shortest paths in a genus g graph. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 89--97."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_14"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM","author":"Demaine E. D.","unstructured":"Demaine , E. D. , Hajiaghayi , M. , and Mohar , B . 2007. Approximation algorithms via contraction decomposition . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM , Philadelphia, PA, 278--287. Demaine, E. D., Hajiaghayi, M., and Mohar, B. 2007. Approximation algorithms via contraction decomposition. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 278--287."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.4.634"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.05.002"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM","author":"Hougardy S.","unstructured":"Hougardy , S. and Pr\u00f6mel , H. J . 1999. A 1.598 approximation algorithm for the Steiner problem in graphs . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM , Philadelphia, PA, 448--453. Hougardy, S. and Pr\u00f6mel, H. J. 1999. A 1.598 approximation algorithm for the Steiner problem in graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 448--453."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009758919736"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649562"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v49:4"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of a Conference in Memory of Claude Berge, Trends in Mathematics. Birkh\u00e4user","author":"Marx D.","year":"2007","unstructured":"Marx , D. 2007 . Precoloring extension on chordal graphs. In Graph Theory in Paris . Proceedings of a Conference in Memory of Claude Berge, Trends in Mathematics. Birkh\u00e4user , Basel, Switzerland, 255--270. Marx, D. 2007. Precoloring extension on chordal graphs. In Graph Theory in Paris. Proceedings of a Conference in Memory of Claude Berge, Trends in Mathematics. Birkh\u00e4user, Basel, Switzerland, 255--270."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.04.002"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_2_1_32_1","unstructured":"Mohar B. and Thomassen C. 2001. Graphs on Surfaces. Johns Hopkins University Press Baltimore MD. Mohar B. and Thomassen C. 2001. Graphs on Surfaces . Johns Hopkins University Press Baltimore MD."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS). Springer","author":"Pr\u00f6mel H. J.","unstructured":"Pr\u00f6mel , H. J. and Steger , A . 1997. RNC-approximation algorithms for the Steiner problem . In Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS). Springer , Berlin, 559--570. Pr\u00f6mel, H. J. and Steger, A. 1997. RNC-approximation algorithms for the Steiner problem. In Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS). Springer, Berlin, 559--570."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230160408"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1007"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00414-0"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70655-1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187035"},{"key":"e_1_2_1_42_1","volume-title":"Better approximation bounds for the network and Euclidean Steiner tree problems. Tech. rep","author":"Zelikovsky A.","unstructured":"Zelikovsky , A. 1996. Better approximation bounds for the network and Euclidean Steiner tree problems. Tech. rep ., University of Virginia , Charlottesville, VA . Zelikovsky, A. 1996. Better approximation bounds for the network and Euclidean Steiner tree problems. Tech. rep., University of Virginia, Charlottesville, VA."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/646341.686725"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2027216.2027219","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2027216.2027219","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:15Z","timestamp":1750278375000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2027216.2027219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["10.1145\/2027216.2027219"],"URL":"https:\/\/doi.org\/10.1145\/2027216.2027219","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10]]},"assertion":[{"value":"2010-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}