Maximale Flüsse in fast-planaren Graphen

Hochstein, Jan M. (2007)
Maximale Flüsse in fast-planaren Graphen.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

URL / URN: urn:nbn:de:tuda-tuprints-8221

Kurzbeschreibung (Abstract)

Das Maximalfluss-Problem ist eines der besterforschten Probleme in der kombinatorischen Optimierung. Gefragt ist hierbei nach dem maximalen statischen Durchsatz durch ein Netzwerk zwischen dem Startknoten s und dem Zielknoten t. Beispiele hierfür sind Netzwerke aus Rohren oder Kabeln oder Strassen- und Schienennetze. Es ist wohlbekannt, dass das Maximalfluss-Problem in planaren Graphen wesentlich schneller gelöst werden kann als in allgemeinen Graphen. Allerdings gibt es bisher keine Ergebnisse für fast-planare Graphen. Mit fast-planar bezeichnen wir Graphen, die wenige nicht-planare Stellen haben, wie zum Beispiel ein Straßennetz mit wenigen Brücken und Tunneln. Dabei ist es a priori nicht klar, wieviel "wenig" ist. Unser Ziel ist es daher, Algorithmen zu finden, die das Maximalfluss-Problem in fast-planaren Graphen asymptotisch schneller lösen als die besten bekannten Algorithmen. Dazu betrachten wir die bekannten Algorithmen für planare Graphen und erweitern sie so, dass sie fast-planare Instanzen optimal lösen. Desweiteren untersuchen wir alle bekannten Lösungsansätze für allgemeine Graphen daraufhin, ob eine Veränderung der Algorithmen oder ihrer Laufzeitbeweise zu Verbesserungen der Laufzeitabschätzung führen. Im Rahmen dieser Untersuchungen finden wir den ersten Algorithmus für ein Fluss-Problem speziell für fast-planare Graphen. Er ist asymptotisch schneller als alle bekannten Algorithmen auf diesen Graphen. Die Anzahl der nicht-planaren Stellen im Graphen geht dabei als Parameter in die Laufzeit ein, sodass sich für Graphen, die näher an der Planarität liegen, eine bessere Laufzeitabschätzung ergibt. Desweiteren finden wir eine einfache Erweiterung eines bekannten Algorithmus, die auf unseren Testinstanzen ein sehr gutes Laufzeitverhalten aufweist. Nebenbei beweisen wir einige neue Beobachtungen für die theoretische Betrachtung des Maximalfluss-Problems. Andererseits können wir auch viele scheinbar erfolgversprechende Überlegungen endgültig widerlegen.

Typ des Eintrags:

Dissertation

Erschienen:

2007

Autor(en):

Hochstein, Jan M.

Art des Eintrags:

Erstveröffentlichung

Titel:

Maximale Flüsse in fast-planaren Graphen

Sprache:

Deutsch

Referenten:

Weihe, Prof. Dr. Karsten ; Kaufmann, Prof. Dr. Michael

Berater:

Weihe, Prof. Dr. Karsten

Publikationsjahr:

5 Juni 2007

Ort:

Darmstadt

Verlag:

Technische Universität

Datum der mündlichen Prüfung:

21 Mai 2007

URL / URN:

urn:nbn:de:tuda-tuprints-8221

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

The maximum flow problem has been widely researched. The task here is to find the maximum throughput through a network from the source s to the sink t. Examples are networks made of cables or tubes and road or railway networks. It is known that the maximum flow problem can be solved much more efficiently in planar graphs than in general graphs. However, there are no results for nearly-planar graphs. By nearly-planar we mean graphs that have a small number of non-planar places such as a road network with a small number of bridges or tunnels. Hereby, it is not known beforehand how we can define this "small number". Our goal is to find algorithms that solve the maximum flow problem in nearly-planar graphs asymptotically faster than previously known algorithms. To this end we consider the known algorithms for planar graphs and improve them to also solve non-planar instances optimally. Furthermore we examine for all known algorithms for the general case whether they or their complexity proofs can be changed to give a better bound on the complexity. During this investigation we find the first algorithms for a flow problem on nearly-planar graphs. This algorithm is asymptotically faster than all previously known algorithms for these graphs. Here the complexity depends on the number of non-planarities in the graph. Thus, th flow in graphs that are nearer to planarity can be computed faster. Moreover we find a simple improvement of a known algorithm that shows a good performance on all of our nearly-planar test instances. Furthermore we show some new theorems on maximum flow algorithms. On the other hand, we are able to disprove some seemingly obvious statements.

Englisch

Freie Schlagworte:

fast-planar, Maximalfluss

Schlagworte: