A new approach for the rainbow spanning forest problem.

Authors :: Moreno, Jorge
Martins, Simone
Frota, Yuri
Source :: Soft Computing - A Fusion of Foundations, Methodologies & Applications. Mar2020, Vol. 24 Issue 5, p3771-3780. 10p.
Publication Year :: 2020
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. [ABSTRACT FROM AUTHOR]

Subjects :: *GRAPH coloring
*INTEGER programming
*RANDOM sets
*GRAPH theory
*GRAPH algorithms
*METAHEURISTIC algorithms

Language :: English
ISSN :: 14327643
Volume :: 24
Issue :: 5
Database :: Academic Search Index
Journal :: Soft Computing - A Fusion of Foundations, Methodologies & Applications
Publication Type :: Academic Journal
Accession number :: 141663203
Full Text :: https://doi.org/10.1007/s00500-019-04145-6