Skip to main content
Erschienen in: Soft Computing 8/2018

16.03.2017 | Methodologies and Application

The rainbow spanning forest problem

verfasst von: Francesco Carrabs, Carmine Cerrone, Raffaele Cerulli, Selene Silvestri

Erschienen in: Soft Computing | Ausgabe 8/2018

Einloggen

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

search-config
loading …

Abstract

Given an undirected and edge-colored graph G, a rainbow component of G is a subgraph of G having all the edges with different colors. The Rainbow Spanning Forest Problem consists of finding a spanning forest of G with the minimum number of rainbow components. The problem is known to be NP-hard on general graphs and on trees. In this paper, we present an integer linear mathematical formulation and a greedy algorithm to solve it. To further improve the results, we applied a multi-start scheme to the greedy algorithm. Computational results are reported on randomly generated instances.

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!

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!

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!

Literatur
Zurück zum Zitat Andrews E, Lumduanhom C, Laforge E, Zhang P (2016) On proper-path colorings in graphs. J Comb Math Comb Comput 97:189–207MathSciNetMATH Andrews E, Lumduanhom C, Laforge E, Zhang P (2016) On proper-path colorings in graphs. J Comb Math Comb Comput 97:189–207MathSciNetMATH
Zurück zum Zitat Carr RD, Doddi S, Konjedov G, Marathe M (2000) On the red-blue set cover problem. In: 11th ACN-SIAM symposium on discrete algorithms, pp 345–353 Carr RD, Doddi S, Konjedov G, Marathe M (2000) On the red-blue set cover problem. In: 11th ACN-SIAM symposium on discrete algorithms, pp 345–353
Zurück zum Zitat Carrabs F, Cerrone C, Cerulli R (2014) A tabu search approach for the circle packing problem. In: 2014 17th International conference on network-based information systems. pp 165–171. IEEE Carrabs F, Cerrone C, Cerulli R (2014) A tabu search approach for the circle packing problem. In: 2014 17th International conference on network-based information systems. pp 165–171. IEEE
Zurück zum Zitat Carrabs F, Cerrone C, Cerulli R, Silvestri S (March 2016) On the complexity of rainbow spanning forest problem. Technical Report 14922, Department od Mathematics, University of Salerno Carrabs F, Cerrone C, Cerulli R, Silvestri S (March 2016) On the complexity of rainbow spanning forest problem. Technical Report 14922, Department od Mathematics, University of Salerno
Zurück zum Zitat Carrabs F, Cerulli R, Dell’Olmo P (2014) A mathematical programming approach for the maximum labeled clique problem. Proced Soc Behav Sci 108:69–78CrossRef Carrabs F, Cerulli R, Dell’Olmo P (2014) A mathematical programming approach for the maximum labeled clique problem. Proced Soc Behav Sci 108:69–78CrossRef
Zurück zum Zitat Cerrone C, Cerull R, Golden B (2017) Carousel greedy: a generalized greedy algorithm with applications in optimization. Comput Oper Res (submitted) Cerrone C, Cerull R, Golden B (2017) Carousel greedy: a generalized greedy algorithm with applications in optimization. Comput Oper Res (submitted)
Zurück zum Zitat Cerrone C, Cerulli R, Gentili M (2015) Vehicle-id sensor location for route flow recognition: models and algorithms. Eur J Oper Res 247(2):618–629MathSciNetCrossRefMATH Cerrone C, Cerulli R, Gentili M (2015) Vehicle-id sensor location for route flow recognition: models and algorithms. Eur J Oper Res 247(2):618–629MathSciNetCrossRefMATH
Zurück zum Zitat Cerulli R, Dell’Olmo P, Gentili M, Raiconi A (2006) Heuristic approaches for the minimum labelling hamiltonian cycle problem. Electron Notes Discret Math 25:131–138MathSciNetCrossRefMATH Cerulli R, Dell’Olmo P, Gentili M, Raiconi A (2006) Heuristic approaches for the minimum labelling hamiltonian cycle problem. Electron Notes Discret Math 25:131–138MathSciNetCrossRefMATH
Zurück zum Zitat Cerulli R, Fink A, Gentili M, Voß S (2005) Metaheuristics comparison for the minimum labelling spanning tree problem. In: The next wave in computing, optimization, and decision technologies. Springer, pp 93–106 Cerulli R, Fink A, Gentili M, Voß S (2005) Metaheuristics comparison for the minimum labelling spanning tree problem. In: The next wave in computing, optimization, and decision technologies. Springer, pp 93–106
Zurück zum Zitat Chang RS, Leu SJ (1997) The minimum labeling spanning trees. Inf Process Lett 63:277–282 Chang RS, Leu SJ (1997) The minimum labeling spanning trees. Inf Process Lett 63:277–282
Zurück zum Zitat Chen Y, Cornick N, Hall AO, Shajpal R, Silberholz J, Yahav I, Golden B (2008) Comparison of heuristics for solving the gmlst problem. In: Telecommunications modeling, policy, and technology. Springer, pp 191–217 Chen Y, Cornick N, Hall AO, Shajpal R, Silberholz J, Yahav I, Golden B (2008) Comparison of heuristics for solving the gmlst problem. In: Telecommunications modeling, policy, and technology. Springer, pp 191–217
Zurück zum Zitat Consoli S, Darby-Dowman K, Mladenović N, Moreno-Pérez JA (2009) Variable neighbourhood search for the minimum labelling steiner tree problem. Ann Oper Res 172:71–96MathSciNetCrossRefMATH Consoli S, Darby-Dowman K, Mladenović N, Moreno-Pérez JA (2009) Variable neighbourhood search for the minimum labelling steiner tree problem. Ann Oper Res 172:71–96MathSciNetCrossRefMATH
Zurück zum Zitat Consoli S, Moreno-Pérez JA, Darby-Dowman K, Mladenović N (2010) Discrete particle swarm optimization for the minimum labelling steiner tree problem. Nat Comput 9:29–46MathSciNetCrossRefMATH Consoli S, Moreno-Pérez JA, Darby-Dowman K, Mladenović N (2010) Discrete particle swarm optimization for the minimum labelling steiner tree problem. Nat Comput 9:29–46MathSciNetCrossRefMATH
Zurück zum Zitat Dantzig GB, Fulkerson DR, Johnson SM (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2:393–410MathSciNet Dantzig GB, Fulkerson DR, Johnson SM (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2:393–410MathSciNet
Zurück zum Zitat Fischetti M, Salazar González JJ, Toth P (1995) Experiments with a multi-commodity formulation for the symmetric capacitated vehicle routing problem. In: Proceedings of the 3rd meeting of the euro working group on transportation. pp 169–173 Fischetti M, Salazar González JJ, Toth P (1995) Experiments with a multi-commodity formulation for the symmetric capacitated vehicle routing problem. In: Proceedings of the 3rd meeting of the euro working group on transportation. pp 169–173
Zurück zum Zitat Jozefowiez N, Laporte G, Semet F (2011) A branch-and-cut algorithm for the minimum labeling hamiltonian cycle problem and two variants. Comput Oper Res 38:1534–1542MathSciNetCrossRefMATH Jozefowiez N, Laporte G, Semet F (2011) A branch-and-cut algorithm for the minimum labeling hamiltonian cycle problem and two variants. Comput Oper Res 38:1534–1542MathSciNetCrossRefMATH
Zurück zum Zitat Silvestri S, Laporte G, Cerulli R (2016) The rainbow cycle cover problem. Networks 68(4):260–270 Silvestri S, Laporte G, Cerulli R (2016) The rainbow cycle cover problem. Networks 68(4):260–270
Zurück zum Zitat Suzuki K (2006) A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph. Gr Comb 22:261–269MathSciNetCrossRefMATH Suzuki K (2006) A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph. Gr Comb 22:261–269MathSciNetCrossRefMATH
Zurück zum Zitat Szachniuk M, De Cola M, Felici G, Błażewicz J (2014) The orderly colored longest path problem-a survey of applications and new algorithms. RAIRO Oper Res 48(1):25–51MathSciNetCrossRefMATH Szachniuk M, De Cola M, Felici G, Błażewicz J (2014) The orderly colored longest path problem-a survey of applications and new algorithms. RAIRO Oper Res 48(1):25–51MathSciNetCrossRefMATH
Zurück zum Zitat Szachniuk M, De Cola M, Felici G, De Werra D, Błażewicz J (2015) Optimal pathway reconstruction on 3d nmr maps. Discret Appl Math 182:134–149MathSciNetCrossRefMATH Szachniuk M, De Cola M, Felici G, De Werra D, Błażewicz J (2015) Optimal pathway reconstruction on 3d nmr maps. Discret Appl Math 182:134–149MathSciNetCrossRefMATH
Zurück zum Zitat Xiong Y, Golden B, Wasil E (2007) The colorful traveling salesman problem. In: Extending the horizons: advances in computing, optimization, and decision technologies. Springer, pp 115–123 Xiong Y, Golden B, Wasil E (2007) The colorful traveling salesman problem. In: Extending the horizons: advances in computing, optimization, and decision technologies. Springer, pp 115–123
Zurück zum Zitat Xiongm Y, Golden B, Wasil E, Chen S (2008) The label-constrained minimum spanning tree problem. In: Telecommunications modeling, policy, and technology, Springer, pp 39–58 Xiongm Y, Golden B, Wasil E, Chen S (2008) The label-constrained minimum spanning tree problem. In: Telecommunications modeling, policy, and technology, Springer, pp 39–58
Metadaten
Titel
The rainbow spanning forest problem
verfasst von
Francesco Carrabs
Carmine Cerrone
Raffaele Cerulli
Selene Silvestri
Publikationsdatum
16.03.2017
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 8/2018
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-017-2540-8

Weitere Artikel der Ausgabe 8/2018

Soft Computing 8/2018 Zur Ausgabe