[Zurück]

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.

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.

http://publik.tuwien.ac.at/files/PubDat_179049.pdf