Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/504
Full metadata record
DC FieldValueLanguage
dc.contributor.authorConsoli, S-
dc.contributor.authorMoreno, J A-
dc.contributor.authorMladenović, N-
dc.contributor.authorDarby-Dowman, K-
dc.coverage.spatial15en
dc.date.accessioned2007-01-12T12:43:03Z-
dc.date.available2007-01-12T12:43:03Z-
dc.date.issued2006-
dc.identifier.urihttp://bura.brunel.ac.uk/handle/2438/504-
dc.description.abstractThis 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.extent240409 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.publisherLa Laguna Universityen
dc.relation.ispartofseriesDEIOC;2006/4, Sep 2006-
dc.subjectMetaheuristicsen
dc.subjectMinimum Labelling Spanning Tree Problemen
dc.subjectNP-harden
dc.subjectPilot Methoden
dc.subjectspanning treesen
dc.subjectconstructive heuristicsen
dc.titleConstructive Heuristics for the Minimum Labelling Spanning Tree Problem: a preliminary comparisonen
dc.typeReporten
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.