{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T21:49:00Z","timestamp":1771710540954,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01758765","type":"journal-article","created":{"date-parts":[[2005,6,15]],"date-time":"2005-06-15T06:49:08Z","timestamp":1118818148000},"page":"309-327","source":"Crossref","is-referenced-by-count":72,"title":["Path-distance heuristics for the Steiner problem in undirected networks"],"prefix":"10.1007","volume":"7","author":[{"given":"Pawel","family":"Winter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"MacGregor Smith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01758765_CR1","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/net.3230100207","volume":"10","author":"Y. P. Aneja","year":"1980","unstructured":"Y. P. Aneja, An integer linear programming approach to the Steiner problem in graphs,Networks 10 (1980), 167\u2013178.","journal-title":"Networks"},{"key":"BF01758765_CR2","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1002\/net.3230170107","volume":"17","author":"A. Balakrishnan","year":"1987","unstructured":"A. Balakrishnan and N. R. Patel, Problem reduction methods and a tree generation algorithm for the Steiner network problem,Networks 17 (1987), 65\u201385.","journal-title":"Networks"},{"key":"BF01758765_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":"BF01758765_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230190102","volume":"19","author":"J. E. Beasley","year":"1989","unstructured":"J. E. Beasley, An SST-based algorithm for the Steiner problem on graphs,Networks 19 (1989), 1\u201316.","journal-title":"Networks"},{"key":"BF01758765_CR5","unstructured":"N. P. Chen, New algorithm for Steiner tree on graphs,IEEE Symp. on Circuits and Systems, 1983, pp. 1217\u20131219."},{"key":"BF01758765_CR6","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S. E. Dreyfus","year":"1971","unstructured":"S. E. Dreyfus and R. A. Wagner, The Steiner problem in graphs,Networks 1 (1971), 195\u2013207.","journal-title":"Networks"},{"key":"BF01758765_CR7","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":"BF01758765_CR8","first-page":"202","volume":"12","author":"C. El-Arbi","year":"1978","unstructured":"C. El-Arbi, Une heuristique pour le probleme de l'arbre de Steiner,RAIRO Rech. Op\u00e9r. 12 (1978), 202\u2013212.","journal-title":"RAIRO Rech. Op\u00e9r."},{"key":"BF01758765_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979."},{"key":"BF01758765_CR10","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 problem in graphs and its implications,Networks 1 (1971), 113\u2013133.","journal-title":"Networks"},{"key":"BF01758765_CR11","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L. Kou","year":"1981","unstructured":"L. Kou, G. Markowsky, and L. Berman, A fast algorithm for Steiner trees,Acta Inform. 15 (1981), 141\u2013145.","journal-title":"Acta Inform."},{"key":"BF01758765_CR12","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J. B. Kruskal","year":"1956","unstructured":"J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem,Proc. Amer. Math. Soc. 7 (1956), 48\u201350.","journal-title":"Proc. Amer. Math. Soc."},{"key":"BF01758765_CR13","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K. Mehlhorn","year":"1988","unstructured":"K. Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs,Inform. Process. Lett. 27 (1988), 125\u2013128.","journal-title":"Inform. Process. Lett."},{"key":"BF01758765_CR14","first-page":"155","volume":"31","author":"J. Plesnik","year":"1981","unstructured":"J. Plesnik, A bound for the Steiner problem in graphs,Math. Solvaca 31 (1981), 155\u2013163.","journal-title":"Math. Solvaca"},{"key":"BF01758765_CR15","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R. C. Prim","year":"1957","unstructured":"R. C. Prim, Shortest connection networks and some generalizations,Bell System Tech. J. 36 (1957), 1389\u20131401.","journal-title":"Bell System Tech. J."},{"key":"BF01758765_CR16","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1080\/0020739830140103","volume":"14","author":"V. J. Rayward-Smith","year":"1983","unstructured":"V. J. Rayward-Smith, The computation of nearly minimal Steiner trees in graphs,Internat. J. Math. Ed. Sci. Tech. 14 (1983), 15\u201323.","journal-title":"Internat. J. Math. Ed. Sci. Tech."},{"key":"BF01758765_CR17","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1002\/net.3230160305","volume":"16","author":"V. J. Rayward-Smith","year":"1986","unstructured":"V. J. Rayward-Smith and A. Clare, On finding Steiner vertices,Networks 16 (1986), 283\u2013294.","journal-title":"Networks"},{"key":"BF01758765_CR18","first-page":"91","volume-title":"Optimization of Connection Structures in Graphs","author":"C. Schiemangk","year":"1985","unstructured":"C. Schiemangk, Thermodynamically motivated simulation for solving the Steiner tree problem and the optimization of interacting path systems, in A. Iwainsky (ed.),Optimization of Connection Structures in Graphs, CICIP, Berlin, 1985, pp. 91\u2013120."},{"key":"BF01758765_CR19","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/net.3230120309","volume":"12","author":"M. L. Shore","year":"1982","unstructured":"M. L. Shore, L. R. Foulds, and P. B. Gibbons, An algorithm for the Steiner problem in graphs,Networks 12 (1982), 323\u2013333.","journal-title":"Networks"},{"key":"BF01758765_CR20","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. Japon. 24 (1980), 573\u2013577.","journal-title":"Math. Japon."},{"key":"BF01758765_CR21","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0020-0190(88)90225-6","volume":"29","author":"B. M. Waxman","year":"1988","unstructured":"B. M. Waxman and M. Imase, Worst-case performance of Rayward-Smith's Steiner tree heuristics,Inform. Process. Lett. 29 (1988), 283\u2013287.","journal-title":"Inform. Process. Lett."},{"key":"BF01758765_CR22","series-title":"Lecture Notes in Computer Science","first-page":"17","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P. Widmayer","year":"1986","unstructured":"P. Widmayer, On approximation algorithms for Steiner's problem in graphs, in G. Tinhofer and G. Schmidt (eds.),Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 246, Springer-Verlag, Berlin, 1986, pp. 17\u201328."},{"key":"BF01758765_CR23","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":"BF01758765_CR24","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"R. T. Wong","year":"1984","unstructured":"R. T. Wong, A dual ascent approach for the Steiner tree problem on a directed graph,Math. Programming 28 (1984), 271\u2013287.","journal-title":"Math. Programming"},{"key":"BF01758765_CR25","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF00289500","volume":"23","author":"Y. F. Wu","year":"1986","unstructured":"Y. F. Wu, P. Widmayer, and C. K. Wong, A faster approximation algorithm for the Steiner problem in graphs,Acta Inform. 23 (1986), 223\u2013229.","journal-title":"Acta Inform."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758765.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01758765\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758765","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T12:25:40Z","timestamp":1557318340000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01758765"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":25,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01758765"],"URL":"https:\/\/doi.org\/10.1007\/bf01758765","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}