TU Darmstadt / ULB / TUprints

Maximale Flüsse in fast-planaren Graphen

Hochstein, Jan M. (2007)
Maximale Flüsse in fast-planaren Graphen.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
np.pdf
Copyright Information: In Copyright.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Maximale Flüsse in fast-planaren Graphen
Language: German
Referees: Weihe, Prof. Dr. Karsten ; Kaufmann, Prof. Dr. Michael
Advisors: Weihe, Prof. Dr. Karsten
Date: 5 June 2007
Place of Publication: Darmstadt
Date of oral examination: 21 May 2007
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.

Alternative Abstract:
Alternative AbstractLanguage

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.

English
Uncontrolled Keywords: fast-planar, Maximalfluss
Alternative keywords:
Alternative keywordsLanguage
fast-planar, MaximalflussGerman
nearly-planar, maximum flowEnglish
URN: urn:nbn:de:tuda-tuprints-8221
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:22
Last Modified: 07 Dec 2012 11:53
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/822
PPN:
Export:
Actions (login required)
View Item View Item