|
Dozent:
Prof. Dr. Klaus Jansen
|
|
|
Bereich:
2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Sonstige prüfbare Vorlesung
|
|
|
Zeit und Ort:
Di 14:10 - 15:40, Hörsaal 2120B
Beginn: 7. November
|
|
|
Übung:
keine Übung
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Vordiplom
|
|
|
Inhalt:
Charakterisierung und Algorithmen für perfekte Graphen
und bestimmte Graphklassen, d.h. Analyse und Erkennung von
Bedingungen, die kombinatorische Probleme,wie
z.B. Färbungsprobleme, einfacher machen. Diese Bedingungen
definieren spezielle Graphklassen:
- bipartite Graphen,
- chordale Graphen,
- Vergleichbarkeitsgraphen,
- Permutationsgraphen,
- Intervallgraphen,
- perfekte Graphen.
Somit ergeben sich folgende Fragestellungen:
- Wie läßt sich eine Graphklasse kombinatorisch
charakterisieren?
- Wie kann man sie algorithmisch erkennen?
- Welche kombinatorischen Besonderheiten bzw. Algorithmen für
Optimierungsprobleme sind für diese Graphklasse bekannt?
|
|
|
Skript:
kein Skript
|
|
|
Literatur:
-
A. Brandstädt:
-
Graphen und Algorithmen
Teubner Verlag, Stuttgart 94.
-
M.C. Golumbic:
-
Algorithmic Graph Theory
Academic Press, New York 80.
-
K. Simon:
-
Effiziente Algorithmen für perfekte Graphen
Teubner Verlag, Stuttgart 92.
|
|
|
Sprechstunde:
siehe hier
|
|
