{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T18:10:28Z","timestamp":1770487828683,"version":"3.49.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["no. 024.002.003 and no. 639.021.438"],"award-info":[{"award-number":["no. 024.002.003 and no. 639.021.438"]}],"id":[{"id":"10.13039\/501100003246","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":[[2020,7,31]]},"abstract":"<jats:p>\n            The S\n            <jats:sc>TEINER<\/jats:sc>\n            T\n            <jats:sc>REE<\/jats:sc>\n            problem is one of the most fundamental NP-complete problems, as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights and a subset of vertices (often called terminals); the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987{ considers instances where the underlying graph is planar and all terminals can be covered by the boundary of\n            <jats:italic>k<\/jats:italic>\n            faces. Erickson et al. show that the problem can be solved by an algorithm using\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>O(k)<\/jats:sup>\n            time and\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>O(k)<\/jats:sup>\n            space, where\n            <jats:italic>n<\/jats:italic>\n            denotes the number of vertices of the input graph. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts.\n          <\/jats:p>\n          <jats:p>\n            In this work, we give an algorithm for P\n            <jats:sc>LANAR<\/jats:sc>\n            S\n            <jats:sc>TEINER<\/jats:sc>\n            T\n            <jats:sc>REE<\/jats:sc>\n            with running time 2\n            <jats:sup>O(k)<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>O(\u221ak)<\/jats:sup>\n            with the above parameterization, using only polynomial space. Furthermore, we show that the running time of our algorithm is almost tight: We prove that there is no\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>o(\u221ak)<\/jats:sup>\n            algorithm for P\n            <jats:sc>LANAR<\/jats:sc>\n            S\n            <jats:sc>TEINER<\/jats:sc>\n            T\n            <jats:sc>REE<\/jats:sc>\n            for any computable function\n            <jats:italic>f<\/jats:italic>\n            , unless the Exponential Time Hypothesis fails.\n          <\/jats:p>","DOI":"10.1145\/3371389","type":"journal-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T00:47:00Z","timestamp":1591490820000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces"],"prefix":"10.1145","volume":"16","author":[{"given":"S\u00e1ndor","family":"Kisfaludi-Bak","sequence":"first","affiliation":[{"name":"Max Planck Institute for Informatics, Saarland Informatics Campus, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":false,"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan van","family":"Leeuwen","sequence":"additional","affiliation":[{"name":"Utrecht University, Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.79"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200110"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02071979"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217004"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Borradaile Glencora"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73951-7_25"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00353-1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1061-2"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 32nd ACM Symposium on Theory of Computing, F. Frances Yao and Eugene M. Luks (Eds.). ACM, 469--478","author":"Danny"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3171-2_8"},{"key":"e_1_2_1_14_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077468"},{"key":"e_1_2_1_17_1","volume-title":"Graph Theory","author":"Diestel Reinhard","edition":"4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_19_1","unstructured":"Ding-Zhu Du and Xiaodong Hu. 2008. Steiner Tree Problems in Computer Communication Networks. World Scientific.  Ding-Zhu Du and Xiaodong Hu. 2008. Steiner Tree Problems in Computer Communication Networks. World Scientific."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2783147.2783151"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9612-z"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_40"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.62"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102788"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1324-4"},{"key":"e_1_2_1_27_1","article-title":"The Steiner Tree Problem","volume":"53","author":"Hwang Frank K.","year":"1992","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.33"},{"key":"e_1_2_1_29_1","volume-title":"Refined vertex sparsifiers of planar graphs. CoRR abs\/1702.05951","author":"Krauthgamer Robert","year":"2017"},{"key":"e_1_2_1_30_1","first-page":"1477","article-title":"Algorithm for the shortest connection of a group of graph vertices","volume":"12","author":"Levin A. Yu.","year":"1971","journal-title":"Soviet Math. Dok."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806735"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_57"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"e_1_2_1_34_1","volume-title":"On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. CoRR abs\/1707.02190","author":"Marx D\u00e1niel","year":"2017"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00052"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214023"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9630-x"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80012-3"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","volume":"20","author":"Pilipczuk Marcin","year":"2013"},{"key":"e_1_2_1_40_1","article-title":"Network sparsification for Steiner problems on planar and bounded-genus graphs","volume":"14","author":"Pilipczuk Marcin","year":"2018","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_41_1","unstructured":"H. J. Pr\u00f6mel and A. Steger. 2012. The Steiner Tree Problem: A Tour through Graphs Algorithms and Complexity. Vieweg+Teubner Verlag.  H. J. Pr\u00f6mel and A. Steger. 2012. The Steiner Tree Problem: A Tour through Graphs Algorithms and Complexity. Vieweg+Teubner Verlag."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217057"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180108"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371389","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:53Z","timestamp":1750199573000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3371389"],"URL":"https:\/\/doi.org\/10.1145\/3371389","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,6]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}