Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Metaheuristics Comparison for the Minimum Labelling Spanning Tree Problem
verfasst von : Raffaele Cerulli, Andreas Fink, Monica Gentili, Stefan Voß
Erschienen in: The Next Wave in Computing, Optimization, and Decision Technologies
Verlag: Springer US
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the
Minimum Labelling Spanning Tree Problem
: Given a graph
G
with a color (label) assigned to each edge (not necessarily properly) we look for a spanning tree of
G
with the minimum number of different colors. The problem has several applications in telecommunication networks, electric networks, multimodal transportation networks, among others, where one aims to ensure connectivity by means of homogeneous connections. For this NP-hard problem very few heuristics are presented in the literature giving good quality solutions. In this paper we apply several metaheuristic approaches to solve the problem. These approaches are able to improve over existing heuristics presented in the literature. Furthermore, a comparison with the results provided by an exact approach existing in the literature shows that we may quite easily obtain optimal or close to optimal solutions.