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.
The rainbow spanning forest problem
CARRABS, FRANCESCO;CERRONE, CARMINE
;CERULLI, Raffaele;SILVESTRI, SELENE
2018-01-01
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
