{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T06:04:09Z","timestamp":1648965849554},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[1991,7,1]],"date-time":"1991-07-01T00:00:00Z","timestamp":678326400000},"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,7]]},"DOI":"10.1007\/bf02067240","type":"journal-article","created":{"date-parts":[[2005,8,14]],"date-time":"2005-08-14T18:06:39Z","timestamp":1124042799000},"page":"537-548","source":"Crossref","is-referenced-by-count":2,"title":["The role of Steiner hulls in the solution to Steiner tree problems"],"prefix":"10.1007","volume":"33","author":[{"given":"J. Scott","family":"Provan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02067240_CR1","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1002\/net.3230070104","volume":"7","author":"A.V. Aho","year":"1977","unstructured":"A.V. Aho, M.R. Garey and H.W. Hwang, Rectilinear Steiner trees: Efficient special-case algorithms, Networks 7(1977)37\u201358.","journal-title":"Networks"},{"key":"BF02067240_CR2","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1002\/net.3230170107","volume":"17","author":"A. Balakrishnan","year":"1987","unstructured":"A. Balakrishnan and W.R. Patel, Problem reduction methods and a tree generation algorithm for the Steiner tree problem, Networks 17(1987)65\u201385.","journal-title":"Networks"},{"key":"BF02067240_CR3","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/net.3230140112","volume":"14","author":"J.E. Beasley","year":"1984","unstructured":"J.E. Beasley, An algorithm for the Steiner problem in graphs, Networks 14(1984)147\u2013159.","journal-title":"Networks"},{"key":"BF02067240_CR4","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1002\/net.3230200110","volume":"20","author":"M. Bern","year":"1990","unstructured":"M. Bern, Faster exact algorithms for Steiner trees in planar networks, Networks 20(1990)109\u2013120.","journal-title":"Networks"},{"key":"BF02067240_CR5","doi-asserted-by":"crossref","unstructured":"M. Bern and D. Bienstock, Polynomially solvable special cases of the Steiner problem in planar networks, Ann. Oper. Res., this volume.","DOI":"10.1007\/BF02071979"},{"key":"BF02067240_CR6","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"M. Bern","year":"1987","unstructured":"M. Bern, E.L. Lawler and R.T. Wong, Linear time computation of optimal subgraphs of decomposable graphs, J. Alg. 8(1987)216\u2013235.","journal-title":"J. Alg."},{"key":"BF02067240_CR7","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 the faces of a planar graph, SIAM J. Comput. 17(1988)53\u201376.","journal-title":"SIAM J. Comput."},{"key":"BF02067240_CR8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1002\/net.3230190107","volume":"19","author":"D. Bienstock","year":"1989","unstructured":"D. Bienstock and C.L. Monma, Optimal enclosing regions in planar graphs, Networks 19(1989)79\u201394.","journal-title":"Networks"},{"key":"BF02067240_CR9","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0167-5060(08)70332-7","volume":"2","author":"F.R.K. Chung","year":"1978","unstructured":"F.R.K. Chung and R.L. Graham, Steiner tree for ladders, Ann. Discr. Math. 2(1978)173\u2013200.","journal-title":"Ann. Discr. Math."},{"key":"BF02067240_CR10","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1137\/0118014","volume":"18","author":"E.J. Cockayne","year":"1970","unstructured":"E.J. Cockayne, On the efficiency of the algorithm for Steiner minimal trees, SIAM J. Appl. Math. 18(1970)150\u2013159.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02067240_CR11","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"E.W. Dreyfus","year":"1972","unstructured":"E.W. Dreyfus and R.A. Wagner, The Steiner problem in graphs, Networks 1(1972)195\u2013207.","journal-title":"Networks"},{"key":"BF02067240_CR12","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0167-6377(89)90005-9","volume":"8","author":"C.W. Duin","year":"1989","unstructured":"C.W. Duin and A. Volgenant, An edge elimination test for the Steiner problem in graphs, Oper. Res. Lett. 8(1989)79\u201383.","journal-title":"Oper. Res. Lett."},{"key":"BF02067240_CR13","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1002\/net.3230190506","volume":"19","author":"C.W. Duin","year":"1989","unstructured":"C.W. Duin and A. Volgenant, Reduction tests for the Steiner problem in graphs, Networks 19(1989)549\u2013567.","journal-title":"Networks"},{"key":"BF02067240_CR14","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":"BF02067240_CR15","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"M.R. Garey, R.L. Graham and D.S. Johnson, The complexity of computing Steiner minimal trees, SIAM J. Appl. Math. 32(1977)835\u2013859.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02067240_CR16","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"M.R. Garey and D.S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math. 32(1977)826\u2013834.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02067240_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"E.N. Gilbert","year":"1968","unstructured":"E.N. Gilbert and H.O. Pollak, Steiner minimal trees, SIAM J. Appl. Math. 16(1968)1\u201329.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02067240_CR18","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R.L. Graham","year":"1972","unstructured":"R.L. Graham, An efficient algorithm for determining the convex hull of a set of points, Info. Proc. Lett. 1(1972)132\u2013133.","journal-title":"Info. Proc. Lett."},{"key":"BF02067240_CR19","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1002\/net.3230010203","volume":"1","author":"S.L. Hakimi","year":"1971","unstructured":"S.L. Hakimi, Steiner's problem in graphs and its implications, Networks 1(1971)113\u2013133.","journal-title":"Networks"},{"key":"BF02067240_CR20","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":"BF02067240_CR21","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF02187919","volume":"3","author":"F.K. Hwang","year":"1988","unstructured":"F.K. Hwang, G.D. Song, G.Y. Ting and D.Z. Hu, A decomposition theorem on Euclidean Steiner minimal trees, Discr. Comp. Geom. 3(1988)367\u2013382.","journal-title":"Discr. Comp. Geom."},{"key":"BF02067240_CR22","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L. Kou","year":"1981","unstructured":"L. Kou, G. Markowski and L. Berman, A fast algorithm for Steiner trees, Acta Informatica 15(1981)141\u2013145.","journal-title":"Acta Informatica"},{"key":"BF02067240_CR23","volume-title":"Construction of Steiner trees with obstacles in the plane","author":"A.L. Liestman","year":"1978","unstructured":"A.L. Liestman, Construction of Steiner trees with obstacles in the plane, Master Thesis, University of Illinois, Urbana-Champaign, Urbana, IL (1978)."},{"key":"BF02067240_CR24","doi-asserted-by":"crossref","first-page":"143","DOI":"10.4153\/CMB-1961-016-2","volume":"4","author":"Z.A. Melzak","year":"1961","unstructured":"Z.A. Melzak, On the problem of Steiner, Can. Math. Bull. 4(1961)143\u2013148.","journal-title":"Can. Math. Bull."},{"key":"BF02067240_CR25","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":"BF02067240_CR26","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":"BF02067240_CR27","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(89)90129-4","volume":"30","author":"J.S. Provan","year":"1989","unstructured":"J.S. Provan, Finding shortest enclosing walks and cycles in embedded graphs, Info. Proc. Lett. 30(1989)119\u2013125.","journal-title":"Info. Proc. Lett."},{"key":"BF02067240_CR28","unstructured":"J.S. Provan, Two new Steiner hull techniques for the Steiner tree problem, Technical Report No. UNC\/OR\/TR-89\/6, Operations Research Department, University of North Carolina at Chapel Hill, NC (1989), Algorithmica (1991), to appear."},{"key":"BF02067240_CR29","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1137\/0132031","volume":"32","author":"A. Rosenthal","year":"1977","unstructured":"A. Rosenthal, Computing the reliability of complex networks, SIAM J. Appl. Math. 32(1977)384\u2013393.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02067240_CR30","unstructured":"P.W. Shor and W.D. Smith, Steiner hulls and\u03c3 hulls, Manuscript (1982)."},{"key":"BF02067240_CR31","volume-title":"Steiner minimal trees with obstacles","author":"J.M. Smith","year":"1982","unstructured":"J.M. Smith, Steiner minimal trees with obstacles, Technical Report, Department of Industrial Engineering and Operations Research, University of Massachusetts, Amherst, MA (1982)."},{"key":"BF02067240_CR32","unstructured":"J.M. Smith and P. Winter, Computational geometry and topological network design,Proc. NATO Advanced Research Workshop on Topological Network Design: Analysis and Synthesis, Gentofte, Denmark (1989)."},{"key":"BF02067240_CR33","first-page":"573","volume":"24","author":"H. Takahashi","year":"1980","unstructured":"H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs, Math. Japonica 24(1980)573\u2013577.","journal-title":"Math. Japonica"},{"key":"BF02067240_CR34","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizeki and N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs. J. ACM 29(1982)623\u2013641.","journal-title":"J. ACM"},{"key":"BF02067240_CR35","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"J.A. Wald","year":"1983","unstructured":"J.A. Wald and C.J. Colbourn, Steiner trees, partial 2-trees, and minimum IFI networks, Networks 13(1983)159\u2013167.","journal-title":"Networks"},{"key":"BF02067240_CR36","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/net.3230150305","volume":"15","author":"P. Winter","year":"1985","unstructured":"P. Winter, An algorithm for the Steiner problem in the Euclidean plane, Networks 15(1985)323\u2013345.","journal-title":"Networks"},{"key":"BF02067240_CR37","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"},{"key":"BF02067240_CR38","unstructured":"Y.Y. Yang and O. Wing, Optimal and suboptimal algorithms for the wiring problem,Proc. IEEE Int. Symp. on Circuit Theory (1972), pp. 154\u2013158."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02067240.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02067240\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02067240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T13:13:30Z","timestamp":1557839610000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02067240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,7]]},"references-count":38,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1991,7]]}},"alternative-id":["BF02067240"],"URL":"https:\/\/doi.org\/10.1007\/bf02067240","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,7]]}}}