{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T21:00:11Z","timestamp":1768683611855,"version":"3.49.0"},"reference-count":23,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":10267,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1978,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We examine the complexity of a classical problem related to the design of centralized computer networks. Under very broad assumptions the problem is shown to be NP\u2010complete, and hence most probably intractable. The same result holds for the \u201cEuclidean\u201d case of the problem; however, in the latter case a simple algorithm produces solutions with relative error almost certainly arbitrarily close to zero.<\/jats:p>","DOI":"10.1002\/net.3230080306","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T08:49:33Z","timestamp":1178873373000},"page":"217-230","source":"Crossref","is-referenced-by-count":131,"title":["The complexity of the capacitated tree problem"],"prefix":"10.1002","volume":"8","author":[{"given":"C. H.","family":"Papadimitriou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"e_1_2_1_4_2","first-page":"538","article-title":"The Traveling Salesman Problem: A Survey","volume":"16","author":"Bellmore M.","year":"1968","journal-title":"J. ORSA"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1972.223452"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030204"},{"key":"e_1_2_1_7_2","unstructured":"Christofides N. \u201cWorst Case Analysis of an Algorithm for the Traveling Salesman Problem \u201d presented in the Carnegie\u2010MellonSymposium on Algorithms and Complexity: New Trends and Ideas Pittsburgh April1976."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.53.0142"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"Garey M. R. R. L.GrahamandD. S.Johnson \u201cSome NP\u2010Complete Geometric Problems \u201dProc. 8th SIGACT Symp. on the Theory of Computing 1976 pp.10\u201322.","DOI":"10.1145\/800113.803626"},{"key":"e_1_2_1_10_2","unstructured":"Garey M. R.andD. S.Johnson \u201cStrong NP\u2010Completeness Results: Motivation Examples and Implications \u201d Bell Laboratories TR Abstract in theProc of the ORSA\u2010TIMS Meeting Miami 1976."},{"issue":"2","key":"e_1_2_1_11_2","first-page":"376","article-title":"Random Minimal Trees","volume":"13","author":"Gillmore E. N.","year":"1965","journal-title":"J. SIAM"},{"key":"e_1_2_1_12_2","unstructured":"Johnson D. S.andS.Lin private communication Bell Laboratories September1976."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_14_2","volume-title":"The Probabilistic Analysis of Some Combinatorial Search Algorithms","author":"Karp R. M.","year":"1976"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040403"},{"key":"e_1_2_1_16_2","unstructured":"Kershenbaum A.andR. R.Boorstyn \u201cCentralized Tele\u2010processing Network Design \u201d Manuscript Network Analysis Corporation 1976."},{"issue":"7","key":"e_1_2_1_17_2","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. Amer. Math. Soc."},{"key":"e_1_2_1_18_2","volume-title":"The Euclidean Traveling Salesman Problem is NP\u2010Complete","author":"Papadimitriou C. H.","year":"1975"},{"key":"e_1_2_1_19_2","unstructured":"Papadimitriou C. H. \u201cThe Complexity of Combinatorial Optimization Problems \u201d Ph. D. Thesis Princeton University 1976."},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"Shamos M. I.andD.Hoey \u201cClosest\u2010Point Problems \u201dProc. 6th Ann. Symp. on Found. Comp. Sci. 1975 pp.151\u2013162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"e_1_2_1_21_2","unstructured":"Sharma R. L.andM. T.El Bardai \u201cSuboptimal Communications Network Synthesis \u201dProc. Internat. Conf. on Communications 1970 pp.19.11\u201319.16."},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","unstructured":"Steiglitz K. P.WeinerandD. J.Kleitman \u201cThe Design of Optimum Cost Survivable Networks \u201dIEEE Trans. on Circuit Theory CT\u201016 1969 pp.455\u2013460.","DOI":"10.1109\/TCT.1969.1083004"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90056-3"},{"key":"e_1_2_1_24_2","unstructured":"Whitney V. K. M. \u201cComparison of Network Topology Optimization Algorithms \u201dProc. Internat. Conf. on Computer Communication 1972 pp.332\u2013337."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230080306","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230080306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T08:43:10Z","timestamp":1699778590000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230080306"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1978,9]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1978,9]]}},"alternative-id":["10.1002\/net.3230080306"],"URL":"https:\/\/doi.org\/10.1002\/net.3230080306","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1978,9]]}}}