Algorithmische Graphentheorie

• Dozent: Alexander Wolff
• Betreuung der Übung: Marc Benkert

Wir werden im Laufe des Semesters in Abhängigkeit der Vorkenntnisse der Hörer eine Teilmenge der folgenden Themen behandeln:

1. Netze und Flüsse [10] mit Anwendungen
   • bipartites Matching
   • Manhattan-Netzwerke [11,12,13]
2. Eulersche Graphen
3. Das Briefträgerproblem in ungerichteten und gerichteten Graphen
4. Hamiltonsche Graphen
5. Das Problem des Handlungsreisenden [14]
   • euklidische minimale Spannbäume [15,16]
   • perfektes Matching mit minimalen Kosten in der Ebene [17]
   • Approximationsalgorithmen und -schemata [18]
6. Vertex Cover und fest-parametrisierte Komplexität [19,20,21]

Dabei sollen abstrakte Graphprobleme durch konkrete Beispiele aus der Praxis und der Geometrie motiviert werden.

Die Vorlesung wendet sich an Hörer im Hauptstudium. Voraussetzung für die Teilnahme ist die Kenntnis der wichtigsten Begriffe aus der Graphentheorie (Zusammenhang, Breiten- und Tiefensuche, Dijkstras Algorithmus, Minimale Spannbäume, Matchings) und der Komplexitätstheorie (Groß-Oh-Notation!), die im Grundstudium eingeführt wurden.

Allgemeine Lehrbücher zum Thema sind [1,3,5,6,7,8,9].

Zusätzliches Material aus der Vorlesung:

1. Netzwerkbeispiel (Max-Flow-Min-Cut)
2. Netzwerkbeispiel (Algorithmus von Edmonds & Karp) aus der Vorlesung
3. Punktemenge für TSP [zum Üben, mit Tour]
4. Parametrisierte Komplexität am Beispiel von Vertex Cover [Folien, 4 pro Seite]

1. Nicos Christofides. Graph Theory: An Algorithmic Approach. Academic Press, New York, 1975.
2. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.
3. Alan Gibbons. Algorithmic Graph Theory. Cambridge University Press, Cambridge, 1985.
4. Manacher. Review of Gibbons, Algorithmic Graph Theory (1985). SIREV: SIAM Review, 31, 1989.
5. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
6. Gary Chartrand and Ortrud R. Oellermann. Applied and Algorithmic Graph Theory. McGraw-Hill, New York, 1993.
7. Krishnaiya Thulasiraman and M. N. S. Swamy. Graphs: Theory and Algorithms. John Wiley & Sons, 1992.
8. Dieter Jungnickel. Graphen, Netzwerke und Algorithmen. BI-Wissenschaftsverlag, Mannheim, 3. edition, 1994.
9. Gabriel Valiente. Algorithms on Trees and Graphs. Springer-Verlag, 2002.
10. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms and Applications. Prentice Hall, 1993.
11. Joachim Gudmundsson, Christos Levcopoulos, and Giri Narasimhan. Approximating a Minimum Manhattan Network. Nordic J. Comput., 8:219-232, 2001.
12. Ryo Kato, Keiko Imai, and Takao Asano. An Improved Algorithm for the Minimum Manhattan Network Problem. In Prosenjit Bose and Pat Morin, editors, Proc. 13th Annual International Symposium on Algorithms and Computation (ISAAC'02), volume 2518 of Lecture Notes in Computer Science, pages 344-356, Vancouver, 20-23 November 2002. Springer-Verlag.
13. Marc Benkert, Takeshi Shirabe, and Alexander Wolff. The Minimum Manhattan Network Problem: Approximations and Exact Solutions. In Proc. 20th European Workshop on Computational Geometry (EWCG'04), Sevilla, 24-26 March 2004.
14. Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinooy Kan, and David B. Shmoys, editors. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons, New York, 1985.
15. Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete Comput. Geom., 6(5):407-422, 1991.
16. Drago Krznaric, Christos Levcopoulos, and Bengt J. Nilsson. Minimum Spanning Trees in d Dimensions. Nordic Journal of Computing, 6(4):446-461, 1999.
17. Kasturi R. Varadarajan. A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane. In Proc. 39th Symp. Foundations of Computer Science (FOCS'98), pages 320-329. IEEE, November 1998.
18. Sanjeev Arora. Approximation schemes for NP-hard geometric optimization problems: a survey. Mathematical Programming, 97(1-2):43-69, July 2003.
19. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer-Verlag, 1999.
20. Rolf Niedermeier and Jochen Alber. Parametrisierte Algorithmen. Vorlesungsskript, 2001. [ps]
21. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms, September 2002. [ps]