Talks and Poster Presentations (with Proceedings-Entry):
M. Berlakovich, M. Ruthmair, G. Raidl:
"A Multilevel Heuristic for the Rooted Delay-Constrained Minimum Spanning Tree Problem";
Talk: International Conference on Computer Aided Systems Theory (Eurocast),
Gran Canaria, Spain;
- 2011-02-11; in: "Proceedings of the 13th International Conference on Computer Aided Systems Theory: Part I",
volume 6927 of LNCS
The rooted delay-constrained minimum spanning tree prob-
lem is an NP-hard combinatorial optimization problem. The problem
appears in practice for example when designing a distribution network
with a guarantee of timely delivery. Another example is be a centralized broadcasting network where the delaybound represents a quality of service constraint. We introduce a multilevel-based construction heuristic which uses a new measurement for the suitability of edges to create a solution for the problem. In comparison to existing heuristics the main intention is not to create a minimum cost spanning tree, but a solution with a high potential for further improvement. Experimental results indicate that in most cases our approach produces solutions that after local improvement are of higher quality than those of other existing construction techniques.
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.