Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Gruber, G. Raidl:
"Solving the Euclidean Bounded Diameter Minimum Spanning Tree Problem by Clustering-Based (Meta-)Heuristics";
Vortrag: International Conference on Computer Aided Systems Theory (Eurocast),
Las Palmas de Gran Canaria, Spanien;
15.02.2009
- 20.02.2009; in: "Computer Aided Systems Theory - EUROCAST 2009, 12th International Conference on Computer Aided Systems Theory",
(2009),
ISBN: 978-3-642-04771-8;
S. 665
- 672.
Kurzfassung englisch:
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.
Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_179049.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.