Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25729
Titel: Algorithms for the Steiner Problem in networks
Sonstige Titel: Algorithmen für das Steiner Problem in Netzwerken
Verfasser: Polzin, Tobias
Sprache: Englisch
Erscheinungsjahr: 2003
SWD-Schlagwörter: Steiner-Problem ; Netzwerk <Graphentheorie> ; Algorithmus
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: The Steiner problem in networks is the problem of connecting a set of required vertices in a weighted graph at minimum cost. It is a classical NP-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 strongest polynomially solvable linear relaxations. On the side of preprocessing techniques, we improve some known reduction tests and introduce powerful new ones. For upper bounds we introduce the successful concept of heuristic reductions. Finally, we integrate these blocks into an exact algorithm. For the exact algorithm and for the different components we present very good computational results on the large benchmark library SteinLib.
Das Steiner Problem in Netzwerken ist das Problem, eine Menge von Basisknoten in einem gewichteten Graphen kostenminimal zu verbinden. Es ist ein klassisches NP-schweres Problem mit vielen Anwendungen. Fuer dieses Problem entwickeln, implementieren und bewerten wir einige neue Techniken. Bezueglich unterer Schranken stellen wir eine Hierarchie von Linearen Relaxationen auf und entwickeln eine Klasse von Relaxationen, die die zur Zeit staerksten polynomiell loesbaren Linearen Relaxationen darstellen. Im Bereich des Preprocessing verbessern wir einige bekannte Reduktionstests und entwickeln einige starke neue Tests. Fuer obere Schranken fuehren wir das erfolgreiche Konzept der "heuristischen Reduktionen'; ein. Schließlich werden diese Bausteine zu einem exakten Algorithmus zusammengesetzt. Sowohl der exakte Algorithmus, als auch die einzelnen Komponenten erzielen sehr gute experimentelle Resultate auf der umfassenden Benchmarkbibliothek SteinLib.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-2182
hdl:20.500.11880/25785
http://dx.doi.org/10.22028/D291-25729
Erstgutachter: Kurt Mehlhorn
Tag der mündlichen Prüfung: 16-Mai-2003
SciDok-Publikation: 6-Mai-2004
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
TobiasPolzin_ProfDrKurtMehlhorn.pdf1,22 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.