Vorlesung Algorithmische Graphentheorie

angeboten im WS 2008/2009
an der Lehr- und Forschungseinheit 5 (Theoretische Informatik)
des Instituts für Informatik der Universität München

Vorlesung

Dr. Felix Brandt, Dr. Jan Johannsen, 2-stündig
Zeit und Ort: Donnerstag, 14.15-15.45 Uhr, Oettingenstr. 67, Oe 1.39
Beginn: 16.10.2008

Übung

Markus Brill, Felix Fischer, 2-stündig
Zeit und Ort: Montag, 16.15-17.45 Uhr, Oettingenstr. 67, Oe 0.43
Beginn: 27.10.2008

Inhalt

Graphen sind kombinatorische Strukturen, die bei der Modellierung zahlreicher Probleme (z.B. in der Routenplanung, im Mobilfunk oder in der künstlichen Intelligenz) hilfreich sind. Die Vorlesung beschäftigt sich mit den algorithmischen Aspekten grundlegender graphentheoretischer Konzepte wie Wegen, Kreisen, Färbungen, Überdeckungen oder Matchings. Neben der Konstruktion von effizienten Algorithmen werden auch Verbindungen zur Komplexitätstheorie hergestellt.

Anforderungen

Teilnahmevorraussetzungen:

Kriterium zur Erlangung eines Scheins: Vorläufige Themenübersicht Folien und Übungsblätter
Folien Übungsblatt
Einführung pdf ---
Graphtraversierung pdf pdf
Euler- und Hamiltonkreise pdf pdf
Knotenüberdeckungen pdf pdf
Knotenfärbungen Teil 1 pdf pdf
Knotenfärbungen Teil 2 pdf pdf
Turniergraphen pdf pdf
Matchings pdf pdf
pdf
Planare Graphen pdf pdf
pdf
pdf

Literatur

Die Vorlesung richtet sich nicht nach einem Lehrbuch. Die Vorlesungsfolien werden jede Woche auf dieser Webseite veröffentlicht. Links