Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Ruthmair, G. Raidl:
"A Kruskal-Based Heuristic for the Rooted Delay-Constrained Minimum Spanning Tree Problem";
Vortrag: International Conference on Computer Aided Systems Theory (Eurocast),
Gran Canaria, Spanien;
15.02.2009
- 20.02.2009; in: "Computer Aided Systems Theory - EUROCAST 2009, volume 5717 of LNCS",
(2009),
ISBN: 978-3-642-04771-8;
S. 713
- 720.
Kurzfassung englisch:
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.
Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_181256.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.