Algorithmic Approaches to the Steiner Problem in Networks


Vahdati Daneshmand, Siavash


[img]
Preview
PDF
dissertationVahdati.pdf - Published

Download (1MB)

URL: https://ub-madoc.bib.uni-mannheim.de/176
URN: urn:nbn:de:bsz:180-madoc-1769
Document Type: Doctoral dissertation
Year of publication: 2004
Publishing house: Universität Mannheim
Evaluator: Krause, Matthias
Date of oral examination: 23 February 2004
Publication language: English
Institution: School of Business Informatics and Mathematics > Theoretische Informatik (Krause)
Subject: 004 Computer science, internet
Classification: CCS: Linear pro Algorithm Combinator Trees Network pr ,
Subject headings (SWD): Netzwerk , Algorithmentheorie
Individual keywords (German): Steinerproblem , Relaxationen , Reduktionen , Heuristiken , Exakte Algorithmen
Keywords (English): Steiner problem , Relaxations , Reductions , Heuristics , Exact algorithms
Abstract: Das Steinerproblem in Netzwerken ist das Problem, in einem gewichteten Graphen eine gegebene Menge von Knoten kostenminimal zu verbinden. Es ist ein klassisches NP-schweres Problem und ein fundamentales Problem bei der Netzwerkoptimierung mit vielen praktischen Anwendungen. Wir nehmen dieses Problem mit verschiedenen Mitteln in Angriff: Relaxationen, die die Zulässigkeitsbedingungen lockern, um eine optimale Lösung annähern zu können; Heuristiken, um gute, aber nicht garantiert optimale Lösungen zu finden; und Reduktionen, um die Probleminstanzen zu vereinfachen, ohne eine optimale Lösung zu zerstören. In allen Fällen untersuchen und verbessern wir bestehende Methoden, stellen neue vor und evaluieren sie experimentell. Wir integrieren diese Bausteine in einen exakten Algorithmus, der den Stand der Algorithmik für die optimale Lösung dieses Problems darstellt. Viele der vorgestellten Methoden können auch für verwandte Probleme von Nutzen sein.
Translation of the title: Algorithmische Ansaetze für das Steinerproblem in Netzwerken (English)
Translation of the abstract: The Steiner problem in networks is the problem of connecting a set of required vertices in a weighted graph at minimum cost. This is a classical NP-hard problem and a fundamental problem in network design with many practical applications. We approach this problem by different means: Relaxations, which relax the feasibility constraints, to get close to an optimal solution; heuristics to find good, but not necessarily optimal solutions; and reductions to simplify problem instances without abandoning the optimal solution. In each case, we study and improve existing methods, introduce new ones, and evaluate them experimentally. We integrate these components into an exact algorithm, which represents the state of the art for the optimal solution of this problem. Many of the presented methods could also be useful for similar problems. (English)
Additional information:

Dieser Eintrag ist Teil der Universitätsbibliographie.

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




+ Citation Example and Export

Vahdati Daneshmand, Siavash (2004) Algorithmic Approaches to the Steiner Problem in Networks. Open Access [Doctoral dissertation]
[img]
Preview


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item