{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T21:20:58Z","timestamp":1775942458900,"version":"3.50.1"},"reference-count":44,"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":8715,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1982,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In recent years we have evidenced an extensive effort in the development of computer communication networks. One of the important aspects of the network design process is the solution of the topological design questions involved in establishing a communication network. In this article, formulations are presented for a variety of centralized network design problems such as the minimal spanning tree problem, capacitated and degree constrained minimal spanning tree problems, The Telpak problem, and, heterogeneous network design problems. The applicability of these formulations to algorithmic development is demonstrated by developing an efficient algorithm for solving the degree constrained minimal spanning tree problem. Computational results are reported for 630 test problems. A Bender's decomposition procedure is developed and tested for the capacitated minimal spanning tree problem with less favorable results.<\/jats:p>","DOI":"10.1002\/net.3230120402","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T13:50:31Z","timestamp":1178891431000},"page":"355-377","source":"Crossref","is-referenced-by-count":202,"title":["Topological design of centralized computer networks\u2014formulations and algorithms"],"prefix":"10.1002","volume":"12","author":[{"given":"Bezalel","family":"Gavish","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":"Proc. Symp. Comput. Commun. Networks and Tele\u2010Traffic","author":"Bahl L. R.","year":"1972"},{"key":"e_1_2_1_3_2","unstructured":"E.BalasandN.Christofides A restricted Lagrangian approach to the traveling salesman problem. Working Paper (1979)."},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"J. F.Benders Partitioning procedures for solving mixed\u2010variables programming problems.Numerische Mathematik. (1962).","DOI":"10.1007\/BF01386316"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1977.1093708"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030204"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1972.223452"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"W.ChouandA.Kershenbaum A unified algorithm for designing multidrop teleprocessing networks.Proc. Data Networks: Analysis and Design 3rd Data Commum. Symp. St. Petersburg FL (1973) pp.148\u2013156.","DOI":"10.1145\/800280.811042"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"M. A.EfroymsonandT. L.Roy A branch\u2010bound algorithm for plant location.Oper. Res.(1966).","DOI":"10.1287\/opre.14.3.361"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","first-page":"1753","DOI":"10.1109\/TCOM.1974.1092122","article-title":"Topological design of multipoint teleprocessing networks","volume":"22","author":"Elian D.","year":"1974","journal-title":"IEEE Trans. Commun."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.53.0142"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1972.8910"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080304"},{"key":"e_1_2_1_15_2","first-page":"206","volume-title":"Computers and Intractability","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_16_2","unstructured":"B.GavishandS. C.Graves The traveling salesman problem and related problems. Working Paper OR 078\u201078 Operations Research Center M.I.T."},{"key":"e_1_2_1_17_2","unstructured":"B.GavishandS. K.Srikanth The dial\u2010a\u2010ride problem\u2010mathematical formulations. Working Paper No. 7909 The Graduate School of Management The University of Rochester Rochester NY (1979)."},{"key":"e_1_2_1_18_2","article-title":"Optimal solution methods for large scale multiple salesman traveling salesman problem","author":"Gavish B.","journal-title":"Manag. Sci."},{"key":"e_1_2_1_19_2","unstructured":"B.Gavish New algorithms for the capacitated minimal directed tree problem\u2014Proceedings of the 1980 IEEE International Conference on Circuits and Computers Portchester NY (October1980)."},{"key":"e_1_2_1_20_2","article-title":"Formulations and algorithms for the capacitated minimal directed tree problem","author":"Gavish B.","journal-title":"JACM"},{"key":"e_1_2_1_21_2","unstructured":"B.Gavish Exact algorithms for solving capacitated minimal spanning tree problems. Working paper The Graduate School of Management The University of Rochester Rochester NY (1982)."},{"key":"e_1_2_1_22_2","unstructured":"B.Gavish Tight linear programming relaxations for the traveling salesman problem. Working paper The Graduate School of Management The University of Rochester Rochester NY (1982)."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120690"},{"key":"e_1_2_1_24_2","first-page":"595","volume-title":"Computer Communications","author":"Green P. E.","year":"1975"},{"key":"e_1_2_1_25_2","unstructured":"D. A.Greenberg A new approach for the optimal placement of concentrators in a remote terminal communications network.Proc. Nat. Telecommun. Conf. Atlanta GA (1973)."},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"M. C.Goldstein Design of long\u2010distance telecommunication networks\u2014the Telepak problem.IEEE Trans. Circuit Theor.CT\u201020 (1973)186\u2013192.","DOI":"10.1109\/TCT.1973.1083655"},{"key":"e_1_2_1_27_2","article-title":"A heuristic configuration procedure for cost minimal communication networks","volume":"666","author":"H\u00e4nsler E.","year":"1974","journal-title":"IBM Res. Report"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040403"},{"key":"e_1_2_1_32_2","unstructured":"A.KershenbaumandR. R.Boorstyn Centralized teleprocessing network design.Proc. Nat. Telecommun. Conf. New Orleans LA (1975) pp.2711\u20132714."},{"key":"e_1_2_1_33_2","doi-asserted-by":"crossref","unstructured":"A.KershenbaumandR.Van Slyke Computing minimum spanning trees efficiently.Proc. ACM Annual Conf.(1972)518\u2013527.","DOI":"10.1145\/800193.569966"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.12.B718"},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1977.1093710"},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080306"},{"key":"e_1_2_1_38_2","first-page":"593","article-title":"A general method of solving extremum problems","volume":"8","author":"Poljak B. T.","year":"1967","journal-title":"Soviet Math. Doklady"},{"key":"e_1_2_1_39_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_40_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.1.156"},{"key":"e_1_2_1_41_2","article-title":"Optimization of TP networks with concentrators and multiconnected terminals","volume":"5149","author":"Tang D. T.","year":"1974","journal-title":"IBM Res. Rep."},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/361284.361299"},{"key":"e_1_2_1_43_2","unstructured":"V. K. M.Whitney Comparison of network topology optimization algorithms. Proc. International Conf. on Computer Communication (1972) pp.332\u2013337."},{"key":"e_1_2_1_44_2","unstructured":"L. S.WooandD. T.Tang Optimization of teleprocessing networks with concentrators.Proc. Natl. Telecommun. Conf. Atlanta GA (1973) pp.37C1\u201337C5."},{"key":"e_1_2_1_45_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.3230120402","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230120402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T13:29:21Z","timestamp":1699795761000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230120402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,12]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1982,12]]}},"alternative-id":["10.1002\/net.3230120402"],"URL":"https:\/\/doi.org\/10.1002\/net.3230120402","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,12]]}}}