Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/3061
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Darby-Dowman, K | - |
dc.contributor.author | Consoli, Sergio | - |
dc.date.accessioned | 2009-02-25T12:12:05Z | - |
dc.date.available | 2009-02-25T12:12:05Z | - |
dc.date.issued | 2008 | - |
dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/3061 | - |
dc.description | This thesis was submitted for the degree of Doctor of Philosophy and awarded by Brunel University. | - |
dc.description.abstract | It is known that graph theoretic models have extensive application to real-life discrete optimization problems. Many of these models are NP-hard and, as a result, exact methods may be impractical for large scale problem instances. Consequently, there is a great interest in developing e±cient approximate methods that yield near-optimal solutions in acceptable computational times. A class of such methods, known as metaheuristics, have been proposed with success. This thesis considers some recently proposed NP-hard combinatorial optimization problems formulated on graphs. In particular, the min- imum labelling spanning tree problem, the minimum labelling Steiner tree problem, and the minimum quartet tree cost problem, are inves- tigated. Several metaheuristics are proposed for each problem, from classical approximation algorithms to novel approaches. A compre- hensive computational investigation in which the proposed methods are compared with other algorithms recommended in the literature is reported. The results show that the proposed metaheuristics outper- form the algorithms recommended in the literature, obtaining optimal or near-optimal solutions in short computational running times. In addition, a thorough analysis of the implementation of these methods provide insights for the implementation of metaheuristic strategies for other graph theoretic problems. | en |
dc.format.extent | 1684876 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | Brunel University, School of Information Systems, Computing and Mathematics PhD Theses | en |
dc.relation.uri | http://bura.brunel.ac.uk/bitstream/2438/3061/1/FulltextThesis.pdf | - |
dc.subject.other | Metaheuristics | en |
dc.subject.other | Combinatorial optimization | en |
dc.subject.other | Graph theory | en |
dc.subject.other | Network theory | en |
dc.subject.other | Labelling tree problems | en |
dc.subject.other | Hierarchical clustering | en |
dc.title | The development and application of metaheuristics for problems in graph theory: A computational study | en |
dc.type | Thesis | - |
Appears in Collections: | Computer Science Dept of Mathematics Theses Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
FulltextThesis.pdf | 1.65 MB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.