Talks and Poster Presentations (with Proceedings-Entry):
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.
English abstract:
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.
Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_181256.pdf
Created from the Publication Database of the Vienna University of Technology.