Advertisement
Published in:
2005 | OriginalPaper | Chapter
Metaheuristics Comparison for the Minimum Labelling Spanning Tree Problem
Authors : Raffaele Cerulli, Andreas Fink, Monica Gentili, Stefan Voß
Published in: The Next Wave in Computing, Optimization, and Decision Technologies
Publisher: Springer US
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.