Seminar
Graphentheoretische Konzepte und Algorithmen (WS97/98)
Überblick
Das Seminar besteht aus zwei wesentlichen Themenblöcken:
- Effiziente Algorithmen zur Bestimmung maximaler und
kostenminimaler Flüsse, sowie
- Approximationsalgorithmen für NP-harte Standort-Probleme auf
Graphen.
Die Seminarvorträge werden ergänzt durch
Fallstudien/Übungen, in denen die Möglichkeit besteht, den
Stoff durch Anwendungen zu vertiefen.
Voraussetzungen
Sinnvolle Voraussetzung für den erfolgreichen Besuch des Seminars sind
Vorkenntnisse über graphentheoretische Methoden und Algorithmen.
Ideal (aber nicht zwingend notwendig) ist der Besuch der Vorlesung
"Graphentheoretische Konzepte und Algorithmen" im
Sommersemester 1997.
Literatur
Die Themen des Seminars beruhen auf den unten angegebenen
Literaturquellen. Für die einzelnen Vorträge sind die
Literaturschlüssel jeweils aufgeführt.
[AMO93] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Networks
flows, Prentice Hall, Englewood Cliffs, New Jersey, 1993.
[CGR97] S. Chaudhuri, N. Garg, and R. Ravi, The p-neighbor
k-center problem, Information Processing Letters (1997), to
appear.
[Hoc97] D.S. Hochbaum (ed.), Approximation algorithms for
NP-hard problems, PWS Publishing Company, 20 Park Plaza,
Boston, MA 02116-4324, 1997.
[LM+91] T. Leighton,F. Makedon, S. Plotkin, C. Stein, E. Tardos, and
S. Tragoudas, Fast approximation algorithms for multicommodity flow
problems, Proceedings of the 23rd Annual ACM Symposium on the
Theory of Computing (STOC'91), 1991, pp. 101-110.
[SK97] S. Schwarz and S.O. Krumke, On budget constrained flow
improvement, Tech. Report 0, University of Würzburg,
Würzburg, Germany, September 1997.
[Vis96] S. Viswanathan, An O(log*n) approximation
algorithm for the asymmetric p-center problem, Proceedings
of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'96),
January 1996, pp. 1-5.
Vortragstermine
- 5. November 1997
Martin Buck:
Ein Preflow-Push Algorithmus für maximale Flüsse
- Literatur: [AMO93, Abschnitt 7.6]
- 12. November 1997
Jan Steffan:
Schnelle Algorithmen für maximale Flüsse
- Literatur: [AMO93, Abschnitte 7.7 und 7.9]
- 19. November 1997
Mathias Schwark:
Kostenminimale Flüsse
- Literatur: [AMO93, Abschnitte 9.3, 9.6 und 9.7]
- 26. November 1997
Simon Weidmann:
Effiziente Algorithmen für kostenminimale Flüsse
- Literatur: [AMO93, Abschnitt 10.2 (und evtl. 10.3)]
- 7. Januar 1998
Surath Sen:
Kreise minimaler Durchschnittskosten
- Literatur: [AMO93, Abschnitte 5.7 und 10.5]
- 14. Januar 1998
Ingo Demgensky:
Ausbau von Flußnetzen
- Literatur: [SK97]
- 21. Januar 1998
Rainer Herrler:
Erweiterungen des k-Center-Problems
- Literatur: [CGR97]
Fallstudien zum Seminar
Hier befindet sich eine postscript-Datei mit
einer kurzen Beschreibung der Seminarthemen.