Talks and Poster Presentations (with Proceedings-Entry):
M. Gruber, G. Raidl:
"Solving the Euclidean Bounded Diameter Minimum Spanning Tree Problem by Clustering-Based (Meta-)Heuristics";
Talk: International Conference on Computer Aided Systems Theory (Eurocast),
Las Palmas de Gran Canaria, Spanien;
2009-02-15
- 2009-02-20; in: "Computer Aided Systems Theory - EUROCAST 2009, 12th International Conference on Computer Aided Systems Theory",
(2009),
ISBN: 978-3-642-04771-8;
665
- 672.
English abstract:
The bounded diameter minimum spanning tree problem is
an NP-hard combinatorial optimization problem arising in particular in
network design. There exist various exact and metaheuristic approaches
addressing this problem, whereas fast construction heuristics are primarily
based on Primīs minimum spanning tree algorithm and fail to produce
reasonable solutions in particular on large Euclidean instances.
In this work we present a method based on hierarchical clustering to
guide the construction process of a diameter constrained tree. Solutions
obtained are further refined using a greedy randomized adaptive search
procedure. Especially on large Euclidean instances with a tight diameter
bound the results are excellent. In this case the solution quality can also
compete with that of a leading metaheuristic.
Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_179049.pdf
Created from the Publication Database of the Vienna University of Technology.