[Back]

M. Gruber, G. Raidl:
"Exploiting hierarchical clustering for finding bounded diameter minimum spanning trees on Euclidean instances";
Talk: GECCO: Genetic and Evolutionary Computation Conference, Montreal, Kanada; 2009-07-08 - 2009-07-12; in: "Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation", (2009), 8 pages.

The bounded diameter minimum spanning tree problem is
an NP-hard combinatorial optimization problem arising, for
example, in network design when quality of service is of
concern. There exist various exact and metaheuristic ap-
proaches 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.
A method based on hierarchical clustering to guide the
construction process of a diameter constrained tree is pre-
sented. Solutions obtained are further re ned using a greedy
randomized adaptive search procedure. Based on the idea of
clustering we also designed a new neighborhood search for
this problem. 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, whereas the computation only needs
a fraction of the time.

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