Algorithms for the Steiner problem in networks [Elektronische Ressource] / von Tobias Polzin
126 Pages

Algorithms for the Steiner problem in networks [Elektronische Ressource] / von Tobias Polzin

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer


Algorithms for the Steiner Problem in NetworksDissertationzur Erlangung des Gradesdes Doktors der Ingenieurswissenschaften (Dr.-Ing.)der Naturwissenschaftlich-Technischen Fakultat¨ Ider Universitat¨ des SaarlandesvonTobias PolzinSaarbruck¨ enMai, 2003Datum des Kolloquiums: 16. Mai 2003Dekan: Professor Dr. Philipp SlusallekGutachter:Professor Dr. Kurt Mehlhorn, MPI fur¨ Informatik, Saarbruck¨ en Dr. William J. Cook, Georgia Institute of Technology, Georgia, USAAbstractThe Steiner problem in networks is the problem of connecting a set of required vertices in aweighted graph at minimum cost. It is a classicalNP-hard problem with many important applications.For this problem we develop, implement and test several new techniques. On the side of lower bounds,we present a hierarchy of linear relaxations and class of new relaxations that are the currently strongestpolynomially solvable linear relaxations. On the side of preprocessing techniques, we improve someknown reduction tests and introduce powerful new ones. For upper bounds we introduce the successfulconcept of heuristic reductions. Finally, we integrate these blocks into an exact algorithm. For the exactalgorithm and for the different components we present very good computational results on the largebenchmark library SteinLib.KurzzusammenfassungDas Steiner Problem in Netzwerken ist das Problem, eine Menge von Basisknoten in einemgewichteten Graphen kostenminimal zu verbinden.



Published by
Published 01 January 2004
Reads 21
Language English
Document size 1 MB