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 |
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. |
URI: | http://bura.brunel.ac.uk/handle/2438/504 |
Appears in Collections: | Publications Dept of Mathematics Research Papers Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Fulltext.pdf | 234.77 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.