{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:25:08Z","timestamp":1750220708232,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T00:00:00Z","timestamp":1583712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme","award":["819416"],"award-info":[{"award-number":["819416"]}]},{"name":"Norwegian Research Council via grant MULTIVAL"},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>\n            A\n            <jats:italic>rectilinear Steiner tree<\/jats:italic>\n            for a set\n            <jats:italic>K<\/jats:italic>\n            of points in the plane is a tree that connects\n            <jats:italic>k<\/jats:italic>\n            using horizontal and vertical lines. In the R\n            <jats:sc>ectilinear<\/jats:sc>\n            S\n            <jats:sc>teiner<\/jats:sc>\n            T\n            <jats:sc>ree<\/jats:sc>\n            problem, the input is a set\n            <jats:italic>K<\/jats:italic>\n            ={\n            <jats:italic>z<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\n            <jats:italic>z<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            ,\u2026,\n            <jats:italic>z<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            } of\n            <jats:italic>n<\/jats:italic>\n            points in the Euclidean plane (R\n            <jats:sup>2<\/jats:sup>\n            ), and the goal is to find a rectilinear Steiner tree for\n            <jats:italic>k<\/jats:italic>\n            of smallest possible total length. A\n            <jats:italic>rectilinear Steiner arborescence<\/jats:italic>\n            for a set\n            <jats:italic>k<\/jats:italic>\n            of points and a root\n            <jats:italic>r<\/jats:italic>\n            \u2208\n            <jats:italic>K<\/jats:italic>\n            is a rectilinear Steiner tree\n            <jats:italic>T<\/jats:italic>\n            for\n            <jats:italic>K<\/jats:italic>\n            such that the path in\n            <jats:italic>T<\/jats:italic>\n            from\n            <jats:italic>r<\/jats:italic>\n            to any point\n            <jats:italic>z<\/jats:italic>\n            \u2208\n            <jats:italic>K<\/jats:italic>\n            is a shortest path. In the R\n            <jats:sc>ectilinear<\/jats:sc>\n            S\n            <jats:sc>teiner<\/jats:sc>\n            A\n            <jats:sc>rborescence<\/jats:sc>\n            problem, the input is a set\n            <jats:italic>K<\/jats:italic>\n            of\n            <jats:italic>n<\/jats:italic>\n            points in R\n            <jats:sup>2<\/jats:sup>\n            , and a root\n            <jats:italic>r<\/jats:italic>\n            \u2208\n            <jats:italic>K<\/jats:italic>\n            , and the task is to find a rectilinear Steiner arborescence for\n            <jats:italic>K<\/jats:italic>\n            , rooted at\n            <jats:italic>r<\/jats:italic>\n            of smallest possible total length. In this article, we design deterministic algorithms for these problems that run in 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\u221a\n              <jats:italic>n<\/jats:italic>\n              log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            time.\n          <\/jats:p>","DOI":"10.1145\/3381420","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T21:33:40Z","timestamp":1583789620000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems"],"prefix":"10.1145","volume":"16","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kharagpur, Kharagpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Hyderabad, Kandi, Sangareddy, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Homi Bhabha National Institute, IRL 2000 ReLaX, and University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,3,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"volume-title":"Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications","author":"Brazil Marcus","key":"e_1_2_1_2_1","unstructured":"Marcus Brazil and Martin Zachariasen . 2015. Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications . Springer . Marcus Brazil and Martin Zachariasen. 2015. Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications. Springer."},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_2_1_3_1","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Micha\u0142 Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer-Verlag . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer-Verlag."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050405"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1324-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00089-4"},{"key":"e_1_2_1_8_1","first-page":"457","article-title":"Improved computation of optimal rectilinear Steiner minimal trees","volume":"7","author":"Ganley Joseph L.","year":"1997","unstructured":"Joseph L. Ganley and James P. Cohoon . 1997 . Improved computation of optimal rectilinear Steiner minimal trees . International Journal of Computational Geometry 7 , 5 (1997), 457 -- 472 . DOI:https:\/\/doi.org\/10.1142\/S0218195997000272 10.1142\/S0218195997000272 Joseph L. Ganley and James P. Cohoon. 1997. Improved computation of optimal rectilinear Steiner minimal trees. International Journal of Computational Geometry 7, 5 (1997), 457--472. DOI:https:\/\/doi.org\/10.1142\/S0218195997000272","journal-title":"International Journal of Computational Geometry"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9627-5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0130013"},{"key":"e_1_2_1_13_1","article-title":"The Steiner Tree Problem","volume":"53","author":"Hwang Frank K.","year":"1992","unstructured":"Frank K. Hwang , Dana S. Richards , and Pawel Winter . 1992 . The Steiner Tree Problem . Annals of Discrete Mathematics , Vol. 53. North-Holland, Amsterdam, Netherlands. Frank K. Hwang, Dana S. Richards, and Pawel Winter. 1992. The Steiner Tree Problem. Annals of Discrete Mathematics, Vol. 53. North-Holland, Amsterdam, Netherlands.","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914). 1812","author":"Philip","year":"1830","unstructured":"Philip N. Klein and D\u00e1niel Marx. 2014. A subexponential parameterized algorithm for Subset TSP on planar graphs . In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914). 1812 -- 1830 . Philip N. Klein and D\u00e1niel Marx. 2014. A subexponential parameterized algorithm for Subset TSP on planar graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914). 1812--1830."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01949715"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9630-x"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913). Leibniz International Proceedings in Informatics","volume":"20","author":"Pilipczuk Marcin","year":"2013","unstructured":"Marcin Pilipczuk , Micha\u0142 Pilipczuk , Piotr Sankowski , and Erik Jan van Leeuwen . 2013 . Subexponential-time parameterized algorithm for Steiner tree on planar graphs . In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913). Leibniz International Proceedings in Informatics , Vol. 20 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 353--364. Marcin Pilipczuk, Micha\u0142 Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. 2013. Subexponential-time parameterized algorithm for Steiner tree on planar graphs. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913). Leibniz International Proceedings in Informatics, Vol. 20. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 353--364."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.37"},{"volume-title":"The Steiner Tree Problem. Friedr. Vieweg 8 Sohn","author":"Pr\u00f6mel Hans J\u00fcrgen","key":"e_1_2_1_20_1","unstructured":"Hans J\u00fcrgen Pr\u00f6mel and Angelika Steger . 2002. The Steiner Tree Problem. Friedr. Vieweg 8 Sohn , Braunschweig, Germany . Hans J\u00fcrgen Pr\u00f6mel and Angelika Steger. 2002. The Steiner Tree Problem. Friedr. Vieweg 8 Sohn, Braunschweig, Germany."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704371353"},{"volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS\u201998)","author":"Warren","key":"e_1_2_1_22_1","unstructured":"Warren D. Smith and Nicholas C. Wormald. 1998. Geometric separator theorems and applications . In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS\u201998) . Warren D. Smith and Nicholas C. Wormald. 1998. Geometric separator theorems and applications. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS\u201998)."},{"key":"e_1_2_1_23_1","volume-title":"Shute","author":"Thomborson Clark D.","year":"1987","unstructured":"Clark D. Thomborson , Linda L. Deneen , and Gary M . Shute . 1987 . Computing a rectilinear Steiner minimal tree in nO(&sqrt;n) time. In Parallel Algorithms and Architectures. Springer , 176--183. Clark D. Thomborson, Linda L. Deneen, and Gary M. Shute. 1987. Computing a rectilinear Steiner minimal tree in nO(&sqrt;n) time. In Parallel Algorithms and Architectures. Springer, 176--183."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381420","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381420","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:06Z","timestamp":1750199586000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381420"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,9]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3381420"],"URL":"https:\/\/doi.org\/10.1145\/3381420","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,3,9]]},"assertion":[{"value":"2017-04-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-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}