CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishGiven 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.
| Titolo: | The rainbow spanning forest problem |
| Autori: | |
| Data di pubblicazione: | 2018 |
| Rivista: | |
| Handle: | http://hdl.handle.net/11567/975055 |
| Appare nelle tipologie: | 01.01 - Articolo su rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | |
|---|---|---|---|
| 2018_RainbowSOCO.pdf | Articolo | Documento in versione editoriale | Administrator Richiedi una copia |
http://hdl.handle.net/11567/975055
Copyright © 2021