{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T18:22:27Z","timestamp":1775758947911,"version":"3.50.1"},"reference-count":23,"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 general Node\u2010Weighted Steiner Tree problem is an extension of the standard Steiner Tree problem by the addition of node\u2010associated weights. This article analyzes a special case of that problem, where the set of nodes, which must be included in the solution tree, consists of a single node, and all node weights are negative. The special case is shown to be NP\u2010Complete, its integer programming formulation is presented, and heuristic procedures are proposed. Using Lagrangian relaxation and subgradient optimization, tight lower bounds were derived and utilized by a branch and bound algorithm. The effectiveness of the developed procedures is demonstrated by a set of computational experiments.<\/jats:p>","DOI":"10.1002\/net.3230170102","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T21:50:44Z","timestamp":1178920244000},"page":"1-17","source":"Crossref","is-referenced-by-count":80,"title":["The node\u2010weighted steiner tree problem"],"prefix":"10.1002","volume":"17","author":[{"given":"Arie","family":"Segev","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.3230100207"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140112"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.6.992"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.1.1"},{"key":"e_1_2_1_8_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey R. M.","year":"1979"},{"key":"e_1_2_1_9_2","unstructured":"B.GavishandS. K.Srikanth Optimal solution methods for large scale multiple traveling salesman problems. Working Paper The Graduate School of Management The University of Rochester Rochester New York (1980)."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120402"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120690"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.20.5.822"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1080\/05695557808975181"},{"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.1287\/opre.18.6.1138"},{"key":"e_1_2_1_16_2","volume-title":"Location on networks: theory and algorithms","author":"Handler G. Y.","year":"1979"},{"key":"e_1_2_1_17_2","volume-title":"Fundamentals of Computer Algorithms","author":"Horowitz E.","year":"1978"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150102"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","unstructured":"R. C.Prim Shortest connection networks and some generalizations Bell Syst. Tech. Jo. (1957)1389\u20131401.","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_20_2","volume-title":"Combinatorial Optimization","author":"Sandi C.","year":"1979"},{"key":"e_1_2_1_21_2","unstructured":"A.Segev Optimizing 2\u2010way joins in fragmented databases systems. Working Paper No. MS\u20102 School of Business Administration University of California Berkeley (1983)."},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120309"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204032"},{"key":"e_1_2_1_24_2","unstructured":"R. T.Wong A dual ascent approach for Steiner tree problems on a directed graph. Report OR&S\u201082\u20133 Department of Mathematical Sciences and Curriculum on OR&S Rensselaer Polytechnic Institute Troy NY1982."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230170102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230170102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T12:22:51Z","timestamp":1697890971000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230170102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,1]]}},"alternative-id":["10.1002\/net.3230170102"],"URL":"https:\/\/doi.org\/10.1002\/net.3230170102","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]]}}}