{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,7]],"date-time":"2023-09-07T16:46:39Z","timestamp":1694105199568},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1991,6]]},"DOI":"10.1007\/bf02071979","type":"journal-article","created":{"date-parts":[[2005,8,14]],"date-time":"2005-08-14T06:42:08Z","timestamp":1124001728000},"page":"403-418","source":"Crossref","is-referenced-by-count":11,"title":["Polynomially solvable special cases of the Steiner problem in planar networks"],"prefix":"10.1007","volume":"33","author":[{"given":"Marshall","family":"Bern","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Bienstock","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02071979_CR1","doi-asserted-by":"crossref","unstructured":"B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs,Proc. 24th IEEE Symp. on Foundations of Computer Science (1983).","DOI":"10.1109\/SFCS.1983.7"},{"key":"BF02071979_CR2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1002\/net.3230200110","volume":"20","author":"M.W. Bern","year":"1990","unstructured":"M.W. Bern, Faster exact algorithms for Steiner trees in planar networks, Networks 20(1990)109\u2013120.","journal-title":"Networks"},{"key":"BF02071979_CR3","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1137\/0217004","volume":"17","author":"D. Bienstock","year":"1988","unstructured":"D. Bienstock and C.L. Monma, On the complexity of covering vertices by faces in a planar graph, SIAM J. Comput. 17(1988)53\u201376.","journal-title":"SIAM J. Comput."},{"key":"BF02071979_CR4","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/BF01840379","volume":"5","author":"D. Bienstock","year":"1990","unstructured":"D. Bienstock and C.L. Monma, On embedding planar graphs to minimize certain distance measures, Algorithmica 5(1990)93\u2013110.","journal-title":"Algorithmica"},{"key":"BF02071979_CR5","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1972","unstructured":"S.E. Dreyfus and R.A. Wagner, The Steiner problem in graphs, Networks 1(1972)195\u2013208.","journal-title":"Networks"},{"key":"BF02071979_CR6","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1287\/moor.12.4.634","volume":"12","author":"R.E. Erickson","year":"1987","unstructured":"R.E. Erickson, C.L. Monma and A.F. Veinott, Send-and-split method for minimum-concave-cost network flows, Math. Oper. Res. 12(1987)634\u2013664.","journal-title":"Math. Oper. Res."},{"key":"BF02071979_CR7","unstructured":"M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979)."},{"key":"BF02071979_CR8","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0114025","volume":"14","author":"M. Hanan","year":"1966","unstructured":"M. Hanan, On Steiner's problem with rectilinear distance, SIAM J. Appl. Math. 14(1966)255\u2013265.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02071979_CR9","unstructured":"F.T. Leighton, private communication (1989)."},{"key":"BF02071979_CR10","first-page":"1477","volume":"12","author":"A.J. Levin","year":"1971","unstructured":"A.J. Levin, Algorithm for the shortest connection of a group of graph vertices, Sov. Math. Doklady 12(1971)1477\u20131481.","journal-title":"Sov. Math. Doklady"},{"key":"BF02071979_CR11","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/net.3230180108","volume":"18","author":"J.S. Provan","year":"1988","unstructured":"J.S. Provan, Convexity and the Steiner tree problem, Networks 18(1988)55\u201372.","journal-title":"Networks"},{"key":"BF02071979_CR12","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1137\/0217057","volume":"17","author":"J.S. Provan","year":"1988","unstructured":"J.S. Provan, An approximation scheme for finding Steiner trees with obstacles, SIAM J. Comput. 17(1988)920\u2013934.","journal-title":"SIAM J. Comput."},{"key":"BF02071979_CR13","unstructured":"W.D. Smith, Studies in computational geometry motivated by mesh generation, Ph.D. Thesis, Department of Mathematics, Princeton University (1988)."},{"key":"BF02071979_CR14","volume-title":"Computing a Rectilinear Steiner Minimal Tree in nO(\u221an) Time, Parallel Algorithms and Architectures","author":"C.D. Thomborson","year":"1987","unstructured":"C.D. Thomborson, L.L. Deneen and G.M. Shute,Computing a Rectilinear Steiner Minimal Tree in n O(\u221an) Time, Parallel Algorithms and Architectures, ed. Albrecht et al. (Akademic-Verlag, Berlin, 1987)."},{"key":"BF02071979_CR15","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1002\/net.3230170203","volume":"17","author":"P. Winter","year":"1987","unstructured":"P. Winter, Steiner problem in networks: A survey, Networks 17(1987)129\u2013167.","journal-title":"Networks"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02071979.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02071979\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02071979","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T20:06:44Z","timestamp":1557778004000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02071979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":15,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF02071979"],"URL":"https:\/\/doi.org\/10.1007\/bf02071979","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}