Termine
Beginn der Vorlesung:
19.04.2006.
| VL |
Mittwoch |
11:00 - 13:00 |
RUD 26, 0’310 |
| Freitag |
11:00 - 13:00 |
RUD 26, 1’305 |
| UE |
Freitag |
09:00 - 11:00 |
RUD 26, 1’305 |
| Sprechzeit |
nach Absprache |
(RUD 25, 3.314) Stefan Hougardy |
Zuordnung
- Hauptstudium, 2. Teil eines Kurses
- Theoretische Informatik
Inhalte und Lernziele
Der Kurs setzt die Vorlesung Graphen und Algorithmen 1 aus dem Wintersemester 2005/2006 fort.
Es werden die folgenden vier Themengebiete vertiefend behandelt:
- Steinerbäume
- zufällige Graphen
- Approximationsalgorithmen und Nichtapproximierbarkeit
- extremale Graphentheorie
Voraussetzungen
- Grundstudium
- Die Kenntnis des ersten Teils der Vorlesung ist wünschenswert, aber nicht notwendig.
Literatur
- Hougardy, Graphen und Algorithmen 1, (Link funktioniert nur von Rechnern des Instituts für Informatik)
- Hougardy, Graphen und Algorithmen 2, (Link funktioniert nur von Rechnern des Instituts für Informatik)
- Hougardy, Proof Checking and Non-Approximability
- Hougardy, Prömel, Steger, Probabilistically checkable proofs and their consequences for approximation algorithms
- Prömel, Steger, The Steiner Tree Problem. A Tour Through Graphs, Algorithms and Complexity
- Emden-Weinert, Hougardy, Kreuter, Prömel, Steger, Einführung in Graphen und Algorithmen
- Diestel, Graphentheorie, Springer Verlag, 2000
- West, Introduction to Graph Theory, Prentice Hall, 1996
English