{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T13:11:34Z","timestamp":1710335494629},"reference-count":25,"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":8533,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Consider a network in which one node is a source having an infinite supply of a commodity, and every other node is a sink having a known constant demand. Furthermore, associated with each potential arc of the network are the following known constants: the cost of constructing the arc, the amount of each scarce resource consumed during the construction of the arc, and the flow capacity of the arc. Given the above known constants as well as the available supply of each of the scarce resources, the problem is to construct a minimal\u2010cost spanning tree subject to the limitations on the consumption of the scarce resources and the requirement that there exists a flow from the source satisfying the demands at the sinks without exceeding any arc capacity. This paper discusses the solution of such a problem by a branch and bound algorithm based on Lagrangian relaxation. Also included are applications of the problem, extensions of the problem, and a report on preliminary computational experience with a computer implementation of the algorithm.<\/jats:p>","DOI":"10.1002\/net.3230130203","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T14:58:51Z","timestamp":1178895531000},"page":"169-190","source":"Crossref","is-referenced-by-count":9,"title":["Constructing a minimal\u2010cost spanning tree subject to resource constraints and flow requirements"],"prefix":"10.1002","volume":"13","author":[{"given":"Andrew W.","family":"Shogan","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.1080\/05695557508975006"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120697"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030204"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0205051"},{"key":"e_1_2_1_6_2","first-page":"357","article-title":"Computational improvements for subgradient optimization","volume":"19","author":"Crowder H. P.","year":"1976","journal-title":"Symp. Math."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_8_2","unstructured":"C. M.DukeandD. F.Moran Earthquakes and city lifelines. InSan Fernando Earthquake of February 9 1971 and Public Policy a report to the Special Subcommittee of the Joint Committee on Seismic Safety of the California Legislature (1971)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.1.1"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120699"},{"key":"e_1_2_1_12_2","unstructured":"B.Gavish Formulations and algorithms for the capacitated minimal directed tree problem University of Rochester Graduate School of Management Working Paper No.8016 (1980)."},{"key":"e_1_2_1_13_2","unstructured":"B.Gavish Topological design of centralized computer networks\u2010Formulations and algorithms University of Rochester Graduate School of Management Working Paper No. 8009. (1981)."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120690"},{"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","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580223"},{"key":"e_1_2_1_18_2","volume-title":"Introduction to Operations Research","author":"Hillier F. S.","year":"1980"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040403"},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"A.KershenbaumandR.Van Slyke Computing minimum spanning trees efficiently.Proc. 25th Ann. Conf. of the ACM(1972) pp.518\u2013527.","DOI":"10.1145\/800193.569966"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.992"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70346-7"},{"key":"e_1_2_1_25_2","unstructured":"A. W.Shogan Constructing a minimal cost spanning tree subject to resource constraints and flow requirements. Stanford University Department of Operations Research and Department of Statistics Technical Report No. 200 (1981)."},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90056-3"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T09:16:30Z","timestamp":1697793390000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,6]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1983,6]]}},"alternative-id":["10.1002\/net.3230130203"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130203","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,6]]}}}