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.
|Digital Object Identifier (DOI):||10.1007/s00500-017-2540-8|
|Codice identificativo Scopus:||2-s2.0-85015632868|
|Titolo:||The rainbow spanning forest problem|
|Appare nelle tipologie:||1.1 Articolo in rivista|