nach oben

Soft Computing

Erschienen in:

21.06.2019 | Methodologies and Application

A new approach for the rainbow spanning forest problem

verfasst von: Jorge Moreno, Simone Martins, Yuri Frota

Erschienen in: Soft Computing | Ausgabe 5/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Given an edge-colored graph G, a tree with all its edges with different colors is called a rainbow tree. The rainbow spanning forest (RSF) problem consists of finding a spanning forest of G, with the minimum number of rainbow trees. In this paper, we present an integer linear programming model for the RSF problem that improves a previous formulation for this problem. A GRASP metaheuristic is also implemented for providing fast primal bounds for the exact method. Computational experiments carried out over a set of random instances show the effectiveness of the strategies adopted in this work, solving problems in graphs with up to 100 vertices.

Vorheriger Artikel Multi-level cognitive concept learning method oriented to data sets with fuzziness: a perspective from features

Nächster Artikel Green supplier selection of electric vehicle charging based on Choquet integral and type-2 fuzzy uncertainty

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

https://www.geekbench.com/geekbench3, [accessed 16-May-2018].

Brualdi RA, Hollingsworth S (2001) Multicolored forests in complete bipartite graphs. Discret Math 240(1–3):239–245MathSciNetCrossRef

Carraher JM, Hartke SG, Horn P (2016) Edge-disjoint rainbow spanning trees in complete graphs. Eur J Comb 57:71–84MathSciNetCrossRef

Carrabs F, Cerrone C, Cerulli R, Silvestri S (2018a) On the complexity of rainbow spanning forest problem. Optim Lett 12:443–454MathSciNetCrossRef

Carrabs F, Cerrone C, Cerulli R, Silvestri S (2018b) The rainbow spanning forest problem. Soft Comput 22(8):2765–2776CrossRef

Hansen P, Mladenovic N (2001) Variable neighbourhood search: principles and applications. Eur J Oper Res 120:449–467CrossRef

Hassin R, Monnot J, Segev D (2007) Approximation algorithms and hardness results for labeled connectivity problems. J Comb Optim 14(4):437–453MathSciNetCrossRef

Kano M, Li X (2008) Monochromatic and heterochromatic subgraphs in edge-colored graphs-a survey. Graphs Comb 24(4):237–263MathSciNetCrossRef

Krumke SO, Wirth HC (1998) On the minimum label spanning tree problem. Inf Process Lett 66(2):81–85MathSciNetCrossRef

Lai X, Zhou Y, He J, Zhang J (2014) Performance analysis of evolutionary algorithms for the minimum label spanning tree problem. IEEE Trans Evol Comput 18(6):860–872CrossRef

Li X, Zhang X (2007) On the minimum monochromatic or multicolored subgraph partition problems. Theor Comput Sci 385(1–3):1–10MathSciNetCrossRef

Moreno J, Martins S, Frota Y (2019) A note on the rainbow cycle cover problem. Networks 73(1):38–47CrossRef

Resende MG, Ribeiro CC (2016) Optimization by GRASP. Springer, BerlinCrossRef

Silvestri S, Laporte G, Cerulli R (2016) The rainbow cycle cover problem. Networks 68(4):260–270MathSciNetCrossRef

Suzuki K (2006) A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph. Graphs and Combinatorics 22(2):261–269MathSciNetCrossRef

Titel: A new approach for the rainbow spanning forest problem
verfasst von: Jorge Moreno
Simone Martins
Yuri Frota
Publikationsdatum: 21.06.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 5/2020
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-019-04145-6

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 5/2020

Uncertain multi-objective optimization for the water–rail–road intermodal transport system with consideration of hub operation process using a memetic algorithm

Multi-criteria group decision making based on ELECTRE I method in Pythagorean fuzzy information

Power-law fitness scaling on multi-objective evolutionary algorithms: interpretations of experimental results

Bipolar fuzzy Dombi prioritized aggregation operators in multiple attribute decision making

A robust fuzzy control approach for path-following control of autonomous vehicles

On interval-valued fuzzy soft set theory applied to semigroups

Premium Partner