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.

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

Created from the Publication Database of the Vienna University of Technology.