{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T16:15:44Z","timestamp":1770480944326,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540739487","type":"print"},{"value":"9783540739517","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73951-7_25","type":"book-chapter","created":{"date-parts":[[2007,8,20]],"date-time":"2007-08-20T06:18:03Z","timestamp":1187590683000},"page":"275-286","source":"Crossref","is-referenced-by-count":8,"title":["Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon"],"prefix":"10.1007","author":[{"given":"Glencora","family":"Borradaile","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip N.","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"25_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial-time approximation schemes for euclidean TSP and other geometric problems. JACM\u00a045(5), 753\u2013782 (1998)","journal-title":"JACM"},{"key":"25_CR2","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1006\/jagm.1994.1041","volume":"17","author":"P. Berman","year":"1994","unstructured":"Berman, P., Ramaiyer, V.: Improved approximations for the Steiner tree problem. Journal of Algorithms\u00a017, 381\u2013408 (1994)","journal-title":"Journal of Algorithms"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/net.3230200110","volume":"20","author":"M. Bern","year":"1990","unstructured":"Bern, M.: Faster exact algorithms for Steiner trees in planar networks. Networks\u00a020, 109\u2013120 (1990)","journal-title":"Networks"},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/BF02071979","volume":"33","author":"M. Bern","year":"1991","unstructured":"Bern, M., Bienstock, D.: Polynomially solvable special cases of the Steiner problem in planar networks. Annals of Operations Research\u00a033, 405\u2013418 (1991)","journal-title":"Annals of Operations Research"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. IPL\u00a032, 171\u2013176 (1989)","journal-title":"IPL"},{"key":"25_CR6","unstructured":"Borradaile, G., Kenyon-Mathieu, C., Klein, P.: A polynomial-time approximation scheme for Steiner tree in planar graphs. In: 18th SODA, pp. 1285\u20131294 (2007)"},{"key":"25_CR7","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1287\/moor.12.4.634","volume":"12","author":"R. Erickson","year":"1987","unstructured":"Erickson, R., Monma, C., Veinott, A.: Send-and-split method for minimum-concave-cost network flows. Mathematics of Operations Research\u00a012, 634\u2013664 (1987)","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"25_CR8","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M. Garey","year":"1977","unstructured":"Garey, M., Johnson, D.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math.\u00a032(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"25_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M. Henzinger","year":"1997","unstructured":"Henzinger, M., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. System Sci.\u00a055(1), 3\u201323 (1997)","journal-title":"J. Comput. System Sci."},{"key":"25_CR10","unstructured":"Hougardy, S., Pr\u00f6mel, H.J.: A 1.598 approximation algorithm for the Steiner problem in graphs. In: 10th SODA, pp. 448\u2013453 (1999)"},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R. Karp","year":"1975","unstructured":"Karp, R.: On the computational complexity of combinatorial problems. Networks\u00a05, 45\u201368 (1975)","journal-title":"Networks"},{"key":"25_CR12","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"M. Karpinski","year":"1997","unstructured":"Karpinski, M., Zelikovsky, A.: New approximation algorithms for the Steiner tree problem. Journal of Combinatorial Optimization\u00a01, 47\u201365 (1997)","journal-title":"Journal of Combinatorial Optimization"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Klein, P.: A linear-time approximation scheme for planar weighted TSP. In: 46th FOCS, p. 647 (2005)","DOI":"10.1109\/SFCS.2005.7"},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L. Kou","year":"1981","unstructured":"Kou, L., Markowsky, G., Berman, L.: A fast algorithm for Steiner trees. Acta Informatica\u00a015, 141\u2013145 (1981)","journal-title":"Acta Informatica"},{"issue":"3","key":"25_CR15","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K. Mehlhorn","year":"1988","unstructured":"Mehlhorn, K.: Approximation algorithm for the Steiner problem in graphs. IPL\u00a027(3), 125\u2013128 (1988)","journal-title":"IPL"},{"issue":"4","key":"25_CR16","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J. Mitchell","year":"1999","unstructured":"Mitchell, J.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM J. Comput.\u00a028(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"25_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/BFb0023489","volume-title":"39th STOC","author":"H.J. Pr\u00f6mel","year":"1997","unstructured":"Pr\u00f6mel, H.J., Steger, A.: RNC approximation algorithms for the Steiner problem. In: 39th STOC. LNCS, vol.\u00a01200, pp. 559\u2013570. Springer, Heidelberg (1997)"},{"key":"25_CR18","doi-asserted-by":"publisher","first-page":"920","DOI":"10.1137\/0217057","volume":"17","author":"J. Provan","year":"1988","unstructured":"Provan, J.: An approximation scheme for finding Steiner trees with obstacles. SIAM J. Comput.\u00a017, 920\u2013934 (1988)","journal-title":"SIAM J. Comput."},{"key":"25_CR19","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/net.3230180108","volume":"18","author":"J. Provan","year":"1988","unstructured":"Provan, J.: Convexity and the Steiner tree problem. Networks\u00a018, 55\u201372 (1988)","journal-title":"Networks"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Rao, S., Smith, W.: Approximating geometrical graphs via spanners and banyans. In: 30th STOC, pp. 540\u2013550 (1998)","DOI":"10.1145\/276698.276868"},{"issue":"1","key":"25_CR21","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G. Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discret. Math.\u00a019(1), 122\u2013134 (2005)","journal-title":"SIAM J. Discret. Math."},{"key":"25_CR22","first-page":"571","volume":"24","author":"H. Takahashi","year":"1980","unstructured":"Takahashi, H., Matsuyama, A.: An approximate solution for the Steiner problem in graphs. Mathematica Japonicae\u00a024, 571\u2013577 (1980)","journal-title":"Mathematica Japonicae"},{"key":"25_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/3-540-17218-1_46","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P. Widmayer","year":"1987","unstructured":"Widmayer, P.: A fast approximation algorithm for Steiner\u2019s problem in graphs. In: Tinhofer, G., Schmidt, G. (eds.) WG 1986. LNCS, vol.\u00a0246, pp. 17\u201328. Springer, Heidelberg (1987)"},{"issue":"2","key":"25_CR24","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF00289500","volume":"23","author":"Y. Wu","year":"1986","unstructured":"Wu, Y., Widmayer, P., Wong, C.: A faster approximation algorithm for the Steiner problem in graphs. Acta informatica\u00a023(2), 223\u2013229 (1986)","journal-title":"Acta informatica"},{"key":"25_CR25","unstructured":"Zelikovsky, A.: Better approximation bounds for the network and Euclidean Steiner tree problems. Technical Report CS-96-06, University of Virginia (1994)"},{"key":"25_CR26","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A. Zelikovsky","year":"1999","unstructured":"Zelikovsky, A.: An 11\/6-approximation algorithm for the network Steiner problem. Algorithmica\u00a09, 463\u2013470 (1999)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73951-7_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:05:53Z","timestamp":1619503553000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73951-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540739487","9783540739517"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73951-7_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}