{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T14:25:06Z","timestamp":1747578306407},"reference-count":15,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":11971,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1974,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An analysis is made of the computational complexity of a class of heuristic algorithms for the solution of the minimal spanning tree problem subject to a restriction on the maximum number (or weight) of nodes in any subtree rooted at a distinguished node. This is of particular interest in designing networks with branch capacity restrictions. The algorithm is a modification of Kruskal's Algorithm where weights are assigned to the nodes and then used, along with the arc lengths, to select the order in which arcs are considered for inclusion in the spanning tree. Considerations in the efficient implementation of such algorithms are examined and several heuristics for assigning node weights are compared.<\/jats:p>","DOI":"10.1002\/net.3230040403","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T02:17:35Z","timestamp":1178849855000},"page":"299-310","source":"Crossref","is-referenced-by-count":41,"title":["Computing capacitated minimal spanning trees efficiently"],"prefix":"10.1002","volume":"4","author":[{"given":"A.","family":"Kershenbaum","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.1109\/T-C.1972.223452"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030204"},{"key":"e_1_2_1_4_2","unstructured":"Elias D.andM. J.Ferguson \u201cTopological Design of Multipoint Teleprocessing Networks \u201d to appear."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","DOI":"10.1090\/S0002-9939-1956-0078686-7","article-title":"On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem","volume":"7","author":"Kruskal J. B.","year":"1956","journal-title":"Proc. of American Math. Society"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.53.0142"},{"key":"e_1_2_1_8_2","unstructured":"Whitney V. K. M. \u201cComparison of Network Topology Optimization Algorithms \u201dProc. of 1972 ICCC 1972 pp.332\u2013337."},{"key":"e_1_2_1_9_2","volume-title":"Mathematical Programming","author":"Reinfeld N. V.","year":"1958"},{"key":"e_1_2_1_10_2","unstructured":"Sharma R. L.andM. T.El\u2010Bardai \u201cSuboptimal Communications Network Synthesis \u201dProc. International Conference on Communications June1970 pp.19.11\u201319.16."},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"Johnson E. \u201cOn Shortest Paths and Sorting \u201dProc. of ACM Annual Conf. August1972 pp.510\u2013517.","DOI":"10.1145\/800193.569965"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"Kershenbaum A.andR.Van Slyke \u201cComputing Minimum Spanning Trees Efficiently \u201dProc. of ACM Annual Conf. August1972 pp.518\u2013527.","DOI":"10.1145\/800193.569966"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010105"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"Chou W.andA.Kershenbaum \u201cA Unified Algorithm for Designing Multidrop Teleprocessing Networks \u201dProc. of Data Com. 73 November1973.","DOI":"10.1145\/800280.811042"},{"key":"e_1_2_1_15_2","volume-title":"\u201cEfficiency of Equivalence Algorithms,\u201d from Complexity of Computer Computations","author":"Fisher M. J.","year":"1972"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400875184"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230040403","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230040403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T14:07:51Z","timestamp":1699798071000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230040403"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,1]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1974,1]]}},"alternative-id":["10.1002\/net.3230040403"],"URL":"https:\/\/doi.org\/10.1002\/net.3230040403","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1974,1]]}}}