Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/504
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Consoli, S | - |
dc.contributor.author | Moreno, J A | - |
dc.contributor.author | Mladenović, N | - |
dc.contributor.author | Darby-Dowman, K | - |
dc.coverage.spatial | 15 | en |
dc.date.accessioned | 2007-01-12T12:43:03Z | - |
dc.date.available | 2007-01-12T12:43:03Z | - |
dc.date.issued | 2006 | - |
dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/504 | - |
dc.description.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. | en |
dc.format.extent | 240409 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | La Laguna University | en |
dc.relation.ispartofseries | DEIOC;2006/4, Sep 2006 | - |
dc.subject | Metaheuristics | en |
dc.subject | Minimum Labelling Spanning Tree Problem | en |
dc.subject | NP-hard | en |
dc.subject | Pilot Method | en |
dc.subject | spanning trees | en |
dc.subject | constructive heuristics | en |
dc.title | Constructive Heuristics for the Minimum Labelling Spanning Tree Problem: a preliminary comparison | en |
dc.type | Report | en |
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.