Graphalgorithmen: Theorie und Praxis

Prof. Dr. Stefan Näher

Vorlesung im Hauptstudium über 4 SWS mit Übungen über 2 SWS

Inhalt
Die Vorlesung befasst sich mit der Entwicklung, Analyse und Implementierung von Algorithmen für Graphen. Dabei sollen die wichtigsten Resultate dieses Gebiets behandelt werden, wie Algorithmen zur Berechnung von Zusammenhangskomponenten, transitive Hüllen, kürzeste Wege, maximale Flüsse und Matchings, Planaritätstests und Zeichnen von Graphen. Insbesondere sollen einige der behandelten Algorithmen unter Verwendung der LEDA-Bibliothek implementiert und experimentell untersucht werden.

Literatur

K. Mehlhorn und S. Näher.
LEDA, a Platform for Combinatorial and Geometric Computing.
Cambridge University Press, 1999

Ahuja, Magnanti, Orlin:
Network Flows, Paramount Publishing International, 1993

 

Nishizeki, Chiba:
Planar Graphs: Theory and Algorithms, Annals of Discrete Mathematics (32), North-Holland, 1988

 

Online-Informationen: http://www.mpi-sb.mpg.de/LEDA

Termine

Last modified on 2004-11-03 by Maria Gindorf.