Vorlesung: Graphen und Algorithmen 2

Dozent: Amin Coja-Oghlan

Termine

Die Vorlesung entfällt am 14.04.2005.

VL	Dienstag	11:00 - 12:30	(RUD 25, 4.112)
VL	Donnerstag	11:00 - 12:30	(RUD 26, 1.305)
UE	Dienstag	09:30 - 11:00	(RUD 25, 4.112)

Zuordnung

Hauptstudium, Halbkurs
Theoretische Informatik

Inhalte und Lernziele

Die Veranstaltung behandelt fortgeschrittene Fragestellungen aus der Kombinatorischen Optimierung, welche mit Hilfe von Graphen modelliert und gelöst werden koennen. Im Zentrum stehen insbesondere Methoden zum Entwurf von exakten effizienten Algorithmen mit Hilfe der Linearen und Semidefiniten Programmierung. Themen sind u.a.:

Lineare Programme und LP-Dualitaet,
Polytope und Graphen: geometrische Hilfsmittel in der Kombinatorischen Optimierung,
das Cliquen- und Faerbungsproblem in perfekten Graphen,
das Travelling-Salesman-Problem,
das Regularitaetslemma und Anwendungen desselben,
Zufaellige Graphen,
Ramseysaetze.

Voraussetzungen

Grundstudium
Die Kenntnis des ersten Teils der Vorlesung ist wünschenswert, aber nicht notwendig.

Literatur

Emden-Weinert, Hougardy, Kreuter, Prömel, Steger, Einführung in Graphen und Algorithmen
Diestel, Graphentheorie, Springer 2000
Groetschel, Lovasz, Schrijver, Geometric algorithms and combinatorial optimization, Springer 1988
Hougardy, Proemel, Graphen und Algorithmen 1
Hougardy, Proemel, Graphen und Algorithmen 2
Schrijver, Combinatorial optimization, Springer 2003

zuletzt geändert am 20.12.2005 (alkox-www)