Output details
11 - Computer Science and Informatics
Middlesex University
Article title
A local search heuristic for bounded-degree minimum spanning trees
Type
D - Journal article
Title of journal
Engineering Optimization
Article number
-
Volume number
40
Issue number
12
First page of article
1115
ISSN of journal
1029-0273
Year of publication
2008
Number of additional authors
4
Additional information
<12> The paper introduces a new genetic local search method for the bounded-degree minimum spanning tree problem, which is NP-complete, contrary to the unbounded case which is solvable in polynomial time. The new approach utilises parameter settings extracted from the analysis of partial fitness landscapes, where the fitness function is determined by the sum of Euclidean distances of nodes. The method is evaluated on ten randomly generated instances and compared to the LWRNG algorithm devised by Li and the EA algorithm proposed by Raidl and Julstrom. The genetic local search method achieves better results than LWRNG and EA on all seven larger problem settings.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
2
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
