[Back]

M. Ruthmair, G. Raidl:
"A Kruskal-Based Heuristic for the Rooted Delay-Constrained Minimum Spanning Tree Problem";
Talk: International Conference on Computer Aided Systems Theory (Eurocast), Gran Canaria, Spanien; 2009-02-15 - 2009-02-20; in: "Computer Aided Systems Theory - EUROCAST 2009, volume 5717 of LNCS", (2009), ISBN: 978-3-642-04771-8; 713 - 720.

The rooted delay-constrained minimum spanning tree problem
is an NP-hard combinatorial optimization problem arising for example
in the design of centralized broadcasting networks where quality of
service constraints are of concern. We present a construction heuristic
based on Kruskal´s algorithm for finding a minimum cost spanning tree
which eliminates some drawbacks of existing heuristic methods. To improve
the solution we introduce a greedy randomized adaptive search procedure
(GRASP) and a variable neighborhood descent (VND) using two
different neighborhood structures. Experimental results indicate that our
approach produces solutions of better quality in shorter runtime when
having strict delay-bounds compared to an existing centralized construction
method based on Prim´s algorithm. Especially when testing on Euclidian
instances our Kruskal-based heuristic outperforms the Prim-based
approach in all scenarios. Moreover our construction heuristic seems to
be a better starting point for subsequent improvement methods.

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