{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:46:36Z","timestamp":1761597996639,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2018,10,10]],"date-time":"2018-10-10T00:00:00Z","timestamp":1539129600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s00500-018-3557-3","type":"journal-article","created":{"date-parts":[[2018,10,10]],"date-time":"2018-10-10T06:47:14Z","timestamp":1539154034000},"page":"2947-2957","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["The Minimum Routing Cost Tree Problem"],"prefix":"10.1007","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8515-736X","authenticated-orcid":false,"given":"Adriano","family":"Masone","sequence":"first","affiliation":[]},{"given":"Maria Elena","family":"Nenni","sequence":"additional","affiliation":[]},{"given":"Antonio","family":"Sforza","sequence":"additional","affiliation":[]},{"given":"Claudio","family":"Sterle","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,10,10]]},"reference":[{"key":"3557_CR1","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1057\/jors.1990.166","volume":"41","author":"JE Beasley","year":"1990","unstructured":"Beasley JE (1990) OR-library: distributing test problems by electronic mail. J Oper Res Soc 41:1069\u20131072","journal-title":"J Oper Res Soc"},{"key":"3557_CR2","doi-asserted-by":"publisher","first-page":"3229","DOI":"10.1016\/j.comnet.2008.08.013","volume":"52","author":"R Campos","year":"2008","unstructured":"Campos R, Ricardo M (2008) A fast algorithm for computing minimum routing cost spanning trees. Comput Netw 52:3229\u20133247","journal-title":"Comput Netw"},{"key":"3557_CR3","doi-asserted-by":"crossref","unstructured":"Chen Y H, Liao G L, Tang C Y (2007) Approximation algorithms for 2-source minimum routing cost k-tree problems. In: Computational science and its applications, ICCSA 2007. Springer, Berlin, pp 520\u2013533","DOI":"10.1007\/978-3-540-74484-9_45"},{"key":"3557_CR4","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1:269\u2013271","journal-title":"Numer Math"},{"key":"3557_CR5","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.endm.2013.05.079","volume":"41","author":"E Fernndez","year":"2013","unstructured":"Fernndez E, Luna-Mota C, Hildenbrandt A, Reinelt G, Wiesberg S (2013) A flow formulation for the optimum communication spanning tree. Electron Notes Discrete Math 41:85\u201392","journal-title":"Electron Notes Discrete Math"},{"key":"3557_CR6","first-page":"161","volume-title":"Exact algorithms for minimum routing cost trees, networks","author":"M Fischetti","year":"2002","unstructured":"Fischetti M, Lancia G, Serafini P (2002) Exact algorithms for minimum routing cost trees, networks. Wiley, London, pp 161\u2013173"},{"key":"3557_CR7","doi-asserted-by":"crossref","unstructured":"Hieu NM, Quoc PT, Nghia ND (2011) An approach of ant algorithm for solving minimum routing cost spanning tree problem. In: Proceedings of the second symposium on information and communication technology, SoICT11. ACM, New York, pp 5\u201310","DOI":"10.1145\/2069216.2069222"},{"key":"3557_CR8","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1137\/0203015","volume":"3","author":"TC Hu","year":"1974","unstructured":"Hu TC (1974) Optimum communication spanning trees. J Comput SIAM 3:188\u2013195","journal-title":"J Comput SIAM"},{"key":"3557_CR9","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1002\/net.3230080402","volume":"8","author":"DS Johnson","year":"1978","unstructured":"Johnson DS, Lenstra JK, Rinnooy Kan AHG (1978) The complexity of the network design problem. Networks 8:279\u2013285","journal-title":"Networks"},{"key":"#cr-split#-3557_CR10.1","unstructured":"Julstrom BA (2001) The blob code: a better string coding of spanning trees for evolutionary search. In: Wu AS"},{"key":"#cr-split#-3557_CR10.2","unstructured":"(ed) 2001 Genetic and evolutionary computation conference workshop program, San Francisco, CA, pp 256-261"},{"key":"3557_CR11","first-page":"585","volume-title":"Proceedings of the genetic and evolutionary computation conference 2005","author":"BA Julstrom","year":"2005","unstructured":"Julstrom BA (2005) The Blob code is competitive with edgesets in genetic algorithms for the minimum routing cost spanning tree problem. In: Beyer H-G et al (eds) Proceedings of the genetic and evolutionary computation conference 2005, vol 1. ACM Press, New York, pp 585\u2013590"},{"key":"3557_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.jpdc.2015.05.006","volume":"83","author":"T Kim","year":"2015","unstructured":"Kim T, Seob SC, Kim D (2015) Distributed formation of degree constrained minimum routing cost tree in wireless ad-hoc networks. J Parallel Distrib Comput 83:143\u2013158","journal-title":"J Parallel Distrib Comput"},{"issue":"6","key":"3557_CR13","doi-asserted-by":"publisher","first-page":"1106","DOI":"10.1007\/s10878-016-0026-8","volume":"33","author":"CW Lin","year":"2017","unstructured":"Lin CW, Wu BY (2017) On the minimum routing cost clustered tree problem. J Comb Optim 33(6):1106\u20131121","journal-title":"J Comb Optim"},{"key":"3557_CR14","first-page":"272","volume-title":"Evolutionary local search for designing peer-to-peer overlay topologies based on minimum routing cost spanning trees, parallel problem solving from nature-PPSN IX","author":"P Merz","year":"2006","unstructured":"Merz P, Wolf S (2006) Evolutionary local search for designing peer-to-peer overlay topologies based on minimum routing cost spanning trees, parallel problem solving from nature-PPSN IX. Springer, Berlin, pp 272\u2013281"},{"key":"3557_CR15","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389\u20131401","journal-title":"Bell Syst Tech J"},{"key":"3557_CR16","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1109\/TEVC.2002.807275","volume":"7","author":"GR Raidl","year":"2003","unstructured":"Raidl GR, Julstrom BA (2003) Edge sets: an effective evolutionary coding of spanning trees. IEEE Trans Evol Comput 7:225\u2013239","journal-title":"IEEE Trans Evol Comput"},{"issue":"1","key":"3557_CR17","first-page":"65","volume":"6","author":"S Sattari","year":"2015","unstructured":"Sattari S, Didehvar F (2015) A metaheuristic algorithm for the minimum routing cost spanning tree problem. Iran J Oper Res 6(1):65\u201378","journal-title":"Iran J Oper Res"},{"issue":"4","key":"3557_CR18","first-page":"153","volume":"10","author":"S Sattari","year":"2013","unstructured":"Sattari S, Didehvar F (2013) Variable neighborhood search approach for the minimum routing cost spanning tree problem. Int J Oper Res 10(4):153\u2013160","journal-title":"Int J Oper Res"},{"key":"3557_CR19","doi-asserted-by":"crossref","unstructured":"Singh A (2008) A new heuristic for the minimum routing cost spanning tree problem. In: Proceedings of 11th international conference on information technology. IEEE Computer Society, pp. 9\u201313","DOI":"10.1109\/ICIT.2008.16"},{"issue":"12","key":"3557_CR20","first-page":"2489","volume":"15","author":"A Singh","year":"2011","unstructured":"Singh A, Sundar S (2011) An artificial bee colony algorithm for the minimum routing cost spanning tree problem. Soft Comput Fus Found Methodol Appl 15(12):2489\u20132499","journal-title":"Soft Comput Fus Found Methodol Appl"},{"key":"3557_CR21","doi-asserted-by":"publisher","first-page":"406","DOI":"10.7763\/IJMLC.2012.V2.154","volume":"2","author":"QP Tan","year":"2012","unstructured":"Tan QP (2012a) A Heuristic approach for solving the minimum routing cost spanning tree problem. Int J Mach Learn Comput, IACSIT 2:406\u2013409","journal-title":"Int J Mach Learn Comput, IACSIT"},{"issue":"4","key":"3557_CR22","doi-asserted-by":"publisher","first-page":"410","DOI":"10.7763\/IJMLC.2012.V2.155","volume":"2","author":"QP Tan","year":"2012","unstructured":"Tan QP (2012b) A genetic approach for solving minimum routing cost spanning tree problem. Int J Mach Learn Comput 2(4):410\u2013414","journal-title":"Int J Mach Learn Comput"},{"key":"3557_CR23","unstructured":"Tan QP, Due NN (2013) An experimental study of minimum routing cost spanning tree algorithms. In: International conference of soft computing and pattern recognition (SoCPaR). IEEE Computer Society, pp 158\u2013165"},{"key":"3557_CR24","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-642-12139-5_24","volume":"6022","author":"S Wolf","year":"2010","unstructured":"Wolf S, Merz P (2010) Efficient cycle search for the minimum routing cost spanning tree problem. Lect Notes Comput Sci 6022:276\u2013287","journal-title":"Lect Notes Comput Sci"},{"key":"3557_CR25","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1137\/0601008","volume":"1","author":"R Wong","year":"1980","unstructured":"Wong R (1980) Worst-case analysis of network design problem heuristics, SIAM. J Algebr Discr Methods 1:51\u201363","journal-title":"J Algebr Discr Methods"},{"key":"3557_CR26","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1137\/S009753979732253X","volume":"29","author":"BY Wu","year":"1999","unstructured":"Wu BY, Lancia G, Bafna V, Chao KM, Ravi R, Tang CY (1999) A polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM J Comp 29:761\u2013778","journal-title":"SIAM J Comp"},{"issue":"3","key":"3557_CR27","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0166-218X(99)00212-7","volume":"102","author":"BY Wu","year":"2000","unstructured":"Wu BY, Chao KM, Tang CY (2000) Approximation algorithms for some optimum communication spanning tree problems. Discrete Appl Math 102(3):245\u2013266","journal-title":"Discrete Appl Math"},{"issue":"2","key":"3557_CR28","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/S0196-6774(02)00205-5","volume":"44","author":"BY Wu","year":"2002","unstructured":"Wu BY (2002) A polynomial time approximation scheme for the two-source minimum routing cost spanning trees. J Algorithms 44(2):359\u2013378","journal-title":"J Algorithms"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-018-3557-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00500-018-3557-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-018-3557-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T19:32:17Z","timestamp":1570649537000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00500-018-3557-3"}},"subtitle":["State of the art and a core-node based heuristic algorithm"],"short-title":[],"issued":{"date-parts":[[2018,10,10]]},"references-count":29,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["3557"],"URL":"https:\/\/doi.org\/10.1007\/s00500-018-3557-3","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"type":"print","value":"1432-7643"},{"type":"electronic","value":"1433-7479"}],"subject":[],"published":{"date-parts":[[2018,10,10]]},"assertion":[{"value":"10 October 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"Adriano Masone declares that he has no conflict of interest. Antonio Sforza declares that he has no conflict of interest. Maria Elena Nenni declares that she has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The research activity of the authors was partially funded by the Department of Electrical Engineering and Information Technology and by the University Federico II of Naples, within the OPT_APP for EPG project (Optimization Approaches for designing and protecting Electric Power Grid) and MOSTOLOG project (A multi-objective approach for Sustainable Logistic System, DIETI-ALTRI_DR408_2017_Ricerca di Ateneo).","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}},{"value":"This article does not contain any studies with human or animals performed by any of the authors.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}