{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:03:47Z","timestamp":1778292227489,"version":"3.51.4"},"reference-count":20,"publisher":"Wiley","issue":"1","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 Steiner network problem seeks a minimum weight connected subgraph that spans a specified subset off nodes in a given graph and optionally uses any of the other nodes as intermediate or Steiner points. This model has a variety of practical applications particularly in location, transportation, and communication planning. In this paper, we first outline some distinctive characteristics of optimal Steiner network solutions and propose a problem reduction procedure based on these properties. We derive a conservative estimate of the expected reduction achieved by this method under one set of probabilistic assumptions and demonstrate that this scheme produces asymptotically optimal reduction. We also report computational results for several randomly generated test problems. We then devise a tree generation algorithm that exploits the special structure of the Steiner network problem while solving its constrained minimal spanning tree formulation.<\/jats:p>","DOI":"10.1002\/net.3230170107","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T21:50:25Z","timestamp":1178920225000},"page":"65-85","source":"Crossref","is-referenced-by-count":36,"title":["Problem reduction methods and a tree generation algorithm for the steiner network problem"],"prefix":"10.1002","volume":"17","author":[{"given":"Anantaram","family":"Balakrishnan","sequence":"first","affiliation":[]},{"given":"Nitin R.","family":"Patel","sequence":"additional","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.3230100207"},{"key":"e_1_2_1_3_2","unstructured":"A.Balakrishnan Formulations and algorithms for the Steiner network problem. Unpublished manuscript Sloan School of Management M.I.T. (1982)."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140112"},{"key":"e_1_2_1_5_2","unstructured":"J. E.Beasley An SST\u2010based algorithm for the Steiner problem in graphs. Working paper Department of Management Science Imperial College London (1985)."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.31.5.803"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_8_2","unstructured":"R. E.Erickson C. L.Monma andA. F.Veinott Jr. Minimum concave\u2010cost network flows. Unpublished manuscript Bell Laboratories Holmdel New Jersey (1979)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.12.9.670"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206011"},{"key":"e_1_2_1_11_2","volume-title":"Computers and Intractibility: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.29.1.49"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010203"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.9.4.643"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1961-016-2"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01949715"},{"key":"e_1_2_1_20_2","first-page":"573","article-title":"An approximate solution for the Steiner problem in graphs","volume":"6","author":"Takahashi H.","year":"1980","journal-title":"Math. Japonica"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02612335"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230170107","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230170107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T12:23:02Z","timestamp":1697890982000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230170107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,1]]}},"alternative-id":["10.1002\/net.3230170107"],"URL":"https:\/\/doi.org\/10.1002\/net.3230170107","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]]}}}