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

Vorlesung: Montag  10 - 12 Uhr HZ 203
  Mittwoch 12 - 14 Uhr HZ 204
Übung: Dienstag  12 - 14 Uhr HZ 204
 
Last modified on 2004-11-03 by Maria Gindorf.