{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T09:53:51Z","timestamp":1722938031187},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0635089"],"id":[{"id":"10.13039\/100000143","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":[[2009,7]]},"abstract":"\n We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n ).\n <\/jats:p>","DOI":"10.1145\/1541885.1541892","type":"journal-article","created":{"date-parts":[[2009,7,8]],"date-time":"2009-07-08T17:28:33Z","timestamp":1247074113000},"page":"1-31","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":51,"title":["An\n O<\/i>\n (\n n<\/i>\n log\n n<\/i>\n ) approximation scheme for Steiner tree in planar graphs"],"prefix":"10.1145","volume":"5","author":[{"given":"Glencora","family":"Borradaile","sequence":"first","affiliation":[{"name":"Brown University, Providence, RI"}]},{"given":"Philip","family":"Klein","sequence":"additional","affiliation":[{"name":"Brown University, Providence, RI"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[{"name":"Brown University, Providence, RI"}]}],"member":"320","published-online":{"date-parts":[[2009,7,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. 33--41","author":"Arora S."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1041"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200110"},{"key":"e_1_2_1_6_1","first-page":"405","article-title":"Polynomially solvable special cases of the Steiner problem in planar networks","volume":"33","author":"Bern M.","year":"1991","journal-title":"Math. Oper. Res."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 1285--1294","author":"Borradaile G."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_40"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 10th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science","volume":"4619","author":"Borradaile G."},{"key":"e_1_2_1_11_1","first-page":"111","article-title":"Note sur un probl\u00e8me de combinaisons","volume":"3","author":"Catalan E.","year":"1838","journal-title":"J. Math\u00e9matiques Pures et Appl."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 367--376","author":"Demaine E. D."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.4.634"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 448--453","author":"Hougardy S."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009758919736"},{"key":"e_1_2_1_20_1","unstructured":"Klein P. A linear-time approximation scheme for planar TSP. SIAM J. Comput. to appear. Klein P. A linear-time approximation scheme for planar TSP. SIAM J. Comput. to appear."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132620"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.7"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 146--155","author":"Klein P. N.","year":"2005"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288961"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90066-X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 14th International Symposium on Theoretical Aspects of Computer Science, 559--570","author":"Pr\u00f6mel H."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217057"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180108"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276868"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_2_1_32_1","unstructured":"Sommerville D. 1929. An Introduction to the Geometry of n Dimensions. London. Sommerville D. 1929. An Introduction to the Geometry of n Dimensions. London."},{"key":"e_1_2_1_33_1","first-page":"571","article-title":"An approximate solution for the Steiner problem in graphs","volume":"24","author":"Takahashi H.","year":"1980","journal-title":"Math. Japonicae"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Tazari S. and M\u00fcller-Hannemann M. 2008. To fear or not to fear large hidden constants: Implementing a planar Steiner tree PTAS. Tech. rep. TUD-CD-2008-2 Technische Universit\u00e4t Darmstadt Department of Computer Science Darmstadt Germany. Tazari S. and M\u00fcller-Hannemann M. 2008. To fear or not to fear large hidden constants: Implementing a planar Steiner tree PTAS. Tech. rep. TUD-CD-2008-2 Technische Universit\u00e4t Darmstadt Department of Computer Science Darmstadt Germany.","DOI":"10.1145\/1963190.2025382"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-21-1-73-84"},{"key":"e_1_2_1_36_1","series-title":"Lecture Notes in Computer Science","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Widmayer P."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289500"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187035"},{"key":"e_1_2_1_39_1","unstructured":"Zelikovsky A. 1994. Better approximation bounds for the network and Euclidean Steiner tree problems. Tech. rep. CS-96-06 University of Virginia. Zelikovsky A. 1994. Better approximation bounds for the network and Euclidean Steiner tree problems. Tech. rep. CS-96-06 University of Virginia."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1541885.1541892","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T06:27:50Z","timestamp":1672295270000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1541885.1541892"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["10.1145\/1541885.1541892"],"URL":"https:\/\/doi.org\/10.1145\/1541885.1541892","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7]]},"assertion":[{"value":"2007-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}