{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T02:07:38Z","timestamp":1774663658554,"version":"3.50.1"},"reference-count":92,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7223,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1987,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of determining a minimum cost connected network (i.e., weighted graph) <jats:italic>G<\/jats:italic> that spans a given subset of vertices is known in the literature as the Steiner problem in networks. We survey exact algorithms and heuristics which appeared in the published literature. We also discuss problems related to the Steiner problem in networks.<\/jats:p>","DOI":"10.1002\/net.3230170203","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T22:18:02Z","timestamp":1178921882000},"page":"129-167","source":"Crossref","is-referenced-by-count":553,"title":["Steiner problem in networks: A survey"],"prefix":"10.1002","volume":"17","author":[{"given":"Pawel","family":"Winter","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070104"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100207"},{"key":"e_1_2_1_4_2","unstructured":"S.ArnborgandA.Proskurowski Characterization and recognition of partial k\u2010trees. Tech. Rep. TRITA\u2010NA\u20108402 Dept. of Numerical Analysis and Computing Science The Royal Inst. of Technology Stockholm Sweden (1984)."},{"key":"e_1_2_1_5_2","unstructured":"S.ArnborgandA.Proskurowski Linear time algorithms for NP\u2010hard problems on graphs embedded in k\u2010trees. Tech. Rep. TRITA\u2010NA\u20108404 Dept. of Numerical Analysis and Computing Science The Royal Inst. of Technology Stockholm Sweden (1984)."},{"key":"e_1_2_1_6_2","unstructured":"A.BalakrishnanandN. R.Patel Problem reduction methods and a tree generation algorithm for the Steiner network problem. Unpublished paper (1985)."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140112"},{"key":"e_1_2_1_8_2","volume-title":"An SST\u2010based algorithm for the Steiner problem in graphs. Tech. Rep","author":"Beasley J. E.","year":"1985"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.3.194"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/355759.355764"},{"key":"e_1_2_1_12_2","unstructured":"W. M.BoyceandJ. B.Seery STEINER72: An improved version of the minimal network problem. Tech. Rep. No. 35 Comp. Sci. Res. Ctr. Bell Laboratories Murray Hill N.J. (undated)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/321724.321733"},{"key":"e_1_2_1_14_2","unstructured":"N.Christofides Worst\u2010case analysis of new heuristic for the traveling salesman problem. Tech. Rep. TR\u2010GSIA Carnegie\u2010Mellon Univ. Pittsburgh Pa. (1976)."},{"key":"e_1_2_1_15_2","first-page":"705","volume-title":"Operational Research '81","author":"Christofides N.","year":"1981"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00149359"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230090103"},{"key":"e_1_2_1_18_2","unstructured":"E. J.CockayneandD. G.Schiller Computation of Steiner minimal trees. In Welsh and Woddall (Eds.) Combinatorics. Inst. Math. Appl. (1972)52\u201371."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230090104"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1051\/ro\/1978120202071","article-title":"Une heuristique pour le probleme de l'arbre de Steiner. R.A.I.R.O","volume":"12","author":"El\u2010Arbi C.","year":"1978","journal-title":"Operations Research"},{"key":"e_1_2_1_23_2","unstructured":"R. E.Erickson C. L.Monma andA. F.VeinottJr. Send\u2010and\u2010split method for minimum\u2010concave\u2010cost network flows. Unpublished paper (1985)."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90154-1"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/0601010"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.1.1"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_28_2","first-page":"1","article-title":"Testing the theory of evolution","volume":"10","author":"Foulds L. R.","year":"1983","journal-title":"Optima"},{"key":"e_1_2_1_29_2","first-page":"215","article-title":"Algorithms for the Steiner problem in graphs","volume":"6","author":"Foulds L. R.","year":"1981","journal-title":"J. Comb. Inf. Syst. Sci."},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(82)80004-3"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1080\/03052158308960625"},{"key":"e_1_2_1_32_2","unstructured":"Y.Fu Application of linear graph theory to printed circuits. Proc. Asilomar Conf. Systems and Circuits (1967)721\u2013728."},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206011"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_35_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_36_2","volume-title":"Integer Programming","author":"Garfinkel R. S.","year":"1972"},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_2_1_39_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010203"},{"key":"e_1_2_1_40_2","unstructured":"M.Hanan Net wiring for large scale integrated circuits. IBM Res. Report RC 1375 (1965)."},{"key":"e_1_2_1_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1972.1083408"},{"key":"e_1_2_1_43_2","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580223"},{"key":"e_1_2_1_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1981.5221152"},{"key":"e_1_2_1_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/0130013"},{"key":"e_1_2_1_47_2","first-page":"303","article-title":"The rectilinear Steiner problem","volume":"2","author":"Hwang F. K.","year":"1978","journal-title":"J. Design Automation Fault Tolerance Anal."},{"key":"e_1_2_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322124"},{"key":"e_1_2_1_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1979.1084551"},{"key":"e_1_2_1_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_51_2","first-page":"349","volume-title":"Proc. 9th Int. Math. Progr. Symp., Budapest 1976","author":"Korhonen P.","year":"1979"},{"key":"e_1_2_1_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288961"},{"key":"e_1_2_1_53_2","unstructured":"J.Krarup The generalized Steiner problem. Unpublished note (1978)."},{"key":"e_1_2_1_54_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_55_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"e_1_2_1_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1976.1084243"},{"key":"e_1_2_1_57_2","first-page":"1477","article-title":"Algorithm for the shortest connection of a group of graph vertices","volume":"12","author":"Levin A. J.","year":"1971","journal-title":"Soviet Math. Dokl."},{"key":"e_1_2_1_58_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.18.1.1"},{"key":"e_1_2_1_59_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120202"},{"key":"e_1_2_1_60_2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1961-016-2"},{"key":"e_1_2_1_61_2","unstructured":"C. L.Monma B. S.Munson andW. R.Pulleyblank Minimum\u2010weight two\u2010connected spanning networks. Unpublished paper."},{"key":"e_1_2_1_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01949715"},{"key":"e_1_2_1_63_2","first-page":"155","article-title":"A bound for the Steiner tree problem in graphs","volume":"31","author":"Plesnik J.","year":"1981","journal-title":"Math. Slovaca"},{"key":"e_1_2_1_64_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_65_2","unstructured":"A.Prodon T. M.Liebling andH.Groflin Steiner's problem on two\u2010trees. Tech. Rep. RO 850315 Dept. de Math. Ecole Polytechnique Federale de Lausanne Suisse (1985)."},{"key":"e_1_2_1_66_2","unstructured":"J. S.Provan Convexity and the Steiner tree problem. Tech. Report 85\/3 Dept. of Operations Research and System Analysis Univ. of North Carolina Chapel Hill (1985)."},{"key":"e_1_2_1_67_2","doi-asserted-by":"publisher","DOI":"10.1080\/0020739830140103"},{"key":"e_1_2_1_68_2","unstructured":"V. J.Rayward\u2010SmithandA.Clare On finding Steiner vertices. Tech. Rep. School of Comp. Studies and Accountancy Univ. of East Anglia (1984)."},{"key":"e_1_2_1_69_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150207"},{"key":"e_1_2_1_70_2","doi-asserted-by":"publisher","DOI":"10.1137\/0203021"},{"key":"e_1_2_1_71_2","unstructured":"A.Segev The node\u2010weighted Steiner tree problem. Tech. Rep. School of Business Administration Univ. of California Berkeley CA. (1985)."},{"key":"e_1_2_1_72_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120309"},{"key":"e_1_2_1_73_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110104"},{"key":"e_1_2_1_74_2","doi-asserted-by":"publisher","DOI":"10.1080\/03052158008902421"},{"key":"e_1_2_1_75_2","doi-asserted-by":"publisher","DOI":"10.1080\/03052157908902401"},{"key":"e_1_2_1_76_2","unstructured":"G. F.Sullivan Approximation algorithms for Steiner tree problems. Tech. Rep. 249 Dept. of Comp. Science Yale Univ. (1982)."},{"key":"e_1_2_1_77_2","first-page":"573","article-title":"An approximate solution for the Steiner problem in graphs","volume":"24","author":"Takahashi H.","year":"1980","journal-title":"Math. Japonica"},{"key":"e_1_2_1_78_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_79_2","unstructured":"J. A.WaldandC. J.Colbourn Steiner trees in probabilistic networks. Tech. Rep. Nr. 82\u20137 Dept. of Comp. Science Univ. of Saskatchewan (1982)."},{"key":"e_1_2_1_80_2","first-page":"15","article-title":"Steiner trees in outerplanar graphs","volume":"36","author":"Wald J. A.","year":"1982","journal-title":"Congr. Numerantium"},{"key":"e_1_2_1_81_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130202"},{"key":"e_1_2_1_82_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150109"},{"key":"e_1_2_1_83_2","unstructured":"P.Winter The Steiner problem. M.Sc. Thesis Inst. of Datalogy Univ. of Copenhagen Denmark (1981)."},{"key":"e_1_2_1_84_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150305"},{"key":"e_1_2_1_85_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01935369"},{"key":"e_1_2_1_86_2","unstructured":"P.Winter Steiner problem in Halin networks. To appear in Discrete Applied Mathematics."},{"key":"e_1_2_1_87_2","article-title":"Generalized Steiner problem in series\u2010parallel networks","author":"Winter P.","journal-title":"J. Algorithms."},{"key":"e_1_2_1_88_2","unstructured":"P.Winter Generalized Steiner problem in Halin networks. In preparation."},{"key":"e_1_2_1_89_2","unstructured":"P.Winter Construction of minimum distance rectangle trees. In preparation."},{"key":"e_1_2_1_90_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02612335"},{"key":"e_1_2_1_91_2","unstructured":"Y. Y.YangandO.Wing An algorithm for the wiring problem. Digest of the IEEE Int. Symp. on Electrical Networks. London (1971)14\u201315."},{"key":"e_1_2_1_92_2","unstructured":"Y. Y.YangandO.Wing Optimal and suboptimal solution algorithms for the wiring problem. Proc. IEEE Int. Symp. Circuit Theory (1972)154\u2013158."},{"key":"e_1_2_1_93_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1972.1083538"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230170203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230170203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T16:25:13Z","timestamp":1697905513000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230170203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,1]]},"references-count":92,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1987,1]]}},"alternative-id":["10.1002\/net.3230170203"],"URL":"https:\/\/doi.org\/10.1002\/net.3230170203","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,1]]}}}