Brunel University Research Archive (BURA) >
University >
Publications >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/504

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
Publication 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.
URI: http://bura.brunel.ac.uk/handle/2438/504
Appears in Collections:Mathematical Science
Publications
Dept of Mathematics Research Papers

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.