In the k-labeled Spanning Forest Problem (kLSF), given a graph G with a label (color) assigned to each edge, and an integer positive value kmax we look for the minimum number of connected components that can be obtained by using at most kmax different labels. The problem is strictly related to the Minimum Labelling Spanning Tree Problem (MLST), since a spanning tree of the graph (i.e. a single connected component) would obviously be an optimal solution for the kLSF, if it can be obtained without violating the bound on kmax. In this work we present heuristic and exact approaches to solve this new problem.
The k-labeled Spanning Forest Problem
CERULLI, Raffaele;GENTILI, Monica;RAICONI, ANDREA
2014
Abstract
In the k-labeled Spanning Forest Problem (kLSF), given a graph G with a label (color) assigned to each edge, and an integer positive value kmax we look for the minimum number of connected components that can be obtained by using at most kmax different labels. The problem is strictly related to the Minimum Labelling Spanning Tree Problem (MLST), since a spanning tree of the graph (i.e. a single connected component) would obviously be an optimal solution for the kLSF, if it can be obtained without violating the bound on kmax. In this work we present heuristic and exact approaches to solve this new problem.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.