In this paper, we present a Branch & Bound algorithm for solving an NP-hard combinatorial optimisation problem denoted as Rainbow Spanning Forest Problem (RSFP). The RSFP consists of finding a spanning forest of an undirected, edge-coloured graph G with the minimum number of rainbow components, where a rainbow component of G is a subgraph of G that has all the edges with different colours. The proposed method is capable of determining the optimal solution within 0.4 s for small instances, thus proving to be computationally competitive with respect to the methods used by the most recent optimisation libraries and commercial SW environments available.
A Branch & Bound Algorithm for the Rainbow Spanning Forest Problem
Cerrone, Carmine;Dragone, Raffaele;Sciomachen, Anna
2026-01-01
Abstract
In this paper, we present a Branch & Bound algorithm for solving an NP-hard combinatorial optimisation problem denoted as Rainbow Spanning Forest Problem (RSFP). The RSFP consists of finding a spanning forest of an undirected, edge-coloured graph G with the minimum number of rainbow components, where a rainbow component of G is a subgraph of G that has all the edges with different colours. The proposed method is capable of determining the optimal solution within 0.4 s for small instances, thus proving to be computationally competitive with respect to the methods used by the most recent optimisation libraries and commercial SW environments available.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
