Name
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.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s00500-019-04145-6 | soft computing |
Keywords | Field | DocType |
Graph theory, Edge-colored graph, Rainbow tree, Metaheuristic, Integer programming | Graph theory,Graph,GRASP,Vertex (geometry),Computer science,Spanning forest,Theoretical computer science,Integer programming,Rainbow,Metaheuristic | Journal |
Volume | Issue | ISSN |
24 | 5 | 1433-7479 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jorge Moreno | 1 | 0 | 0.34 |
| Simone L. Martins | 2 | 253 | 20.94 |
| Yuri Frota | 3 | 105 | 13.98 |