Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Soft Computing
Published in: Soft Computing 8/2018

16-03-2017 | Methodologies and Application

The rainbow spanning forest problem

Authors: Francesco Carrabs, Carmine Cerrone, Raffaele Cerulli, Selene Silvestri

Published in: Soft Computing | Issue 8/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

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.
previous article Improved fuzzy C-means clustering in the process of exudates detection using mathematical morphology

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Literature
Andrews E, Lumduanhom C, Laforge E, Zhang P (2016) On proper-path colorings in graphs. J Comb Math Comb Comput 97:189–207MathSciNetMATH
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
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, Silvestri S (March 2016) On the complexity of rainbow spanning forest problem. Technical Report 14922, Department od Mathematics, University of Salerno
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
Cerrone C, Cerull R, Golden B (2017) Carousel greedy: a generalized greedy algorithm with applications in optimization. Comput Oper Res (submitted)
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
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, 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
Chang RS, Leu SJ (1997) The minimum labeling spanning trees. Inf Process Lett 63:277–282
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
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, 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
Dantzig GB, Fulkerson DR, Johnson SM (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2:393–410MathSciNet
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
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
Silvestri S, Laporte G, Cerulli R (2016) The rainbow cycle cover problem. Networks 68(4):260–270
Suzuki K (2006) A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph. Gr Comb 22:261–269MathSciNetCrossRefMATH
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, De Werra D, Błażewicz J (2015) Optimal pathway reconstruction on 3d nmr maps. Discret Appl Math 182:134–149MathSciNetCrossRefMATH
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
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
Metadata
Title
The rainbow spanning forest problem
Authors
Francesco Carrabs
Carmine Cerrone
Raffaele Cerulli
Selene Silvestri
Publication date
16-03-2017
Publisher
Springer Berlin Heidelberg
Published in
Soft Computing / Issue 8/2018
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-017-2540-8

Other articles of this Issue 8/2018

Soft Computing 8/2018 Go to the issue

Methodologies and Application

The example application of genetic algorithm for the framework of cultural and creative brand design in Tamsui Historical Museum

Methodologies and Application

Detecting and quantifying ambiguity: a neural network approach

Methodologies and Application

SAR image edge detection via sparse representation

Foundations

On central limit theorems for IV-events

Methodologies and Application

A sophisticated PSO based on multi-level adaptation and purposeful detection

Methodologies and Application

Adaptive contents for interactive TV guided by machine learning based on predictive sentiment analysis of data

Premium Partner

    Image Credits