Please use this identifier to cite or link to this item:
Title: Constructive Heuristics for the Minimum Labelling Spanning Tree Problem: a preliminary comparison
Authors: Consoli, S
Moreno, J A
Mladenović, N
Darby-Dowman, K
Keywords: Metaheuristics;Minimum Labelling Spanning Tree Problem;NP-hard;Pilot Method;spanning trees;constructive heuristics
Issue Date: 2006
Publisher: La Laguna University
Series/Report no.: DEIOC;2006/4, Sep 2006
Abstract: This report studies constructive heuristics for the minimum labelling spanning tree (MLST) problem. The purpose is to find a spanning tree that uses edges that are as similar as possible. Given an undirected labeled connected graph (i.e., with a label or color for each edge), the minimum labeling spanning tree problem seeks a spanning tree whose edges have the smallest possible number of distinct labels. The model can represent many real-world problems in telecommunication networks, electric networks, and multimodal transportation networks, among others, and the problem has been shown to be NP-complete even for complete graphs. A primary heuristic, named the maximum vertex covering algorithm has been proposed. Several versions of this constructive heuristic have been proposed to improve its efficiency. Here we describe the problem, review the literature and compare some variants of this algorithm.
Appears in Collections:Publications
Dept of Mathematics Research Papers
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
Fulltext.pdf234.77 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.