nach oben

Soft Computing

Erschienen in:

10.10.2018 | Focus

The Minimum Routing Cost Tree Problem

State of the art and a core-node based heuristic algorithm

verfasst von: Adriano Masone, Maria Elena Nenni, Antonio Sforza, Claudio Sterle

Erschienen in: Soft Computing | Ausgabe 9/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The minimum routing cost tree problem arises when we need to find the tree minimizing the minimum travel/communication cost, i.e., the tree which presents the minimal difference with the same cost computed on the whole network. This paper provides the state of the art of the problem and proposes a new heuristic based on the identification of a core of the network around which the solution can be built. The algorithm has been tested on literature instances of up to one thousand nodes. The results, compared with those of other heuristic algorithms, prove the competitiveness of the proposed one both in terms of the quality of the solution and computation time.

Vorheriger Artikel Checking weak optimality and strong boundedness in interval linear programming

Nächster Artikel An effective heuristic for large-scale fault-tolerant k-median problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Beasley JE (1990) OR-library: distributing test problems by electronic mail. J Oper Res Soc 41:1069–1072CrossRef

Campos R, Ricardo M (2008) A fast algorithm for computing minimum routing cost spanning trees. Comput Netw 52:3229–3247CrossRefMATH

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–533

Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1:269–271MathSciNetCrossRefMATH

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–92CrossRef

Fischetti M, Lancia G, Serafini P (2002) Exact algorithms for minimum routing cost trees, networks. Wiley, London, pp 161–173MATH

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–10

Hu TC (1974) Optimum communication spanning trees. J Comput SIAM 3:188–195MathSciNetCrossRefMATH

Johnson DS, Lenstra JK, Rinnooy Kan AHG (1978) The complexity of the network design problem. Networks 8:279–285MathSciNetCrossRefMATH

Julstrom BA (2001) The blob code: a better string coding of spanning trees for evolutionary search. In: Wu AS (ed) 2001 Genetic and evolutionary computation conference workshop program, San Francisco, CA, pp 256–261

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–590

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–158CrossRef

Lin CW, Wu BY (2017) On the minimum routing cost clustered tree problem. J Comb Optim 33(6):1106–1121MathSciNetCrossRefMATH

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–281

Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389–1401CrossRef

Raidl GR, Julstrom BA (2003) Edge sets: an effective evolutionary coding of spanning trees. IEEE Trans Evol Comput 7:225–239CrossRef

Sattari S, Didehvar F (2015) A metaheuristic algorithm for the minimum routing cost spanning tree problem. Iran J Oper Res 6(1):65–78

Sattari S, Didehvar F (2013) Variable neighborhood search approach for the minimum routing cost spanning tree problem. Int J Oper Res 10(4):153–160MathSciNet

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–13

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–2499

Tan QP (2012a) A Heuristic approach for solving the minimum routing cost spanning tree problem. Int J Mach Learn Comput, IACSIT 2:406–409CrossRef

Tan QP (2012b) A genetic approach for solving minimum routing cost spanning tree problem. Int J Mach Learn Comput 2(4):410–414CrossRef

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–165

Wolf S, Merz P (2010) Efficient cycle search for the minimum routing cost spanning tree problem. Lect Notes Comput Sci 6022:276–287MathSciNetCrossRef

Wong R (1980) Worst-case analysis of network design problem heuristics, SIAM. J Algebr Discr Methods 1:51–63CrossRefMATH

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–778MathSciNetCrossRefMATH

Wu BY, Chao KM, Tang CY (2000) Approximation algorithms for some optimum communication spanning tree problems. Discrete Appl Math 102(3):245–266MathSciNetCrossRefMATH

Wu BY (2002) A polynomial time approximation scheme for the two-source minimum routing cost spanning trees. J Algorithms 44(2):359–378MathSciNetCrossRefMATH

Titel: The Minimum Routing Cost Tree Problem
State of the art and a core-node based heuristic algorithm
verfasst von: Adriano Masone
Maria Elena Nenni
Antonio Sforza
Claudio Sterle
Publikationsdatum: 10.10.2018
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 9/2019
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-018-3557-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 9/2019

A distributed hybrid index for processing continuous range queries over moving objects

Self-adaptive parameters in differential evolution based on fitness performance with a perturbation strategy

Scheduling ships movements within a canal harbor

A decision support system to improve performances of airport check-in services

Sparse analytic hierarchy process: an experimental analysis

MIP-based heuristic approaches for the capacitated edge activation problem: the effect of non-compactness