Termine
Beginn der Vorlesung:
18.04.2001
| VL |
Montag |
11:00 - 13:00 |
(RUD 25, 3.101) |
| Mittwoch |
11:00 - 13:00 |
(RUD 25, 3.101) |
| UE |
Mittwoch |
13:00 - 15:00 |
(RUD 25, 3.101) |
| PR |
n.V. |
Zuordnung
- Hauptstudium, 2. Teil eines Kurses
- Theoretische Informatik
Voraussetzungen
- Grundstudium
- Die Kenntnis des ersten Teils der Vorlesung ist wünschenswert, aber nicht notwendig.
Inhalte und Lernziele
Der Kurs setzt die Vorlesung Graphen und Algorithmen 1 aus dem Wintersemester 2000/2001 fort.
Es werden die folgenden vier Themengebiete vertiefend behandelt:
- Steinerbäume
- zufällige Graphen
- Approximationsalgorithmen und Nichtapproximierbarkeit
- extremale Graphentheorie
Empfohlene Literatur
-
Hougardy, Prömel,
Graphen und Algorithmen 1
-
Hougardy, Prömel,
Graphen und Algorithmen 2
-
Hougardy,
Proof Checking and Non-Approximability
-
Hougardy, Prömel, Steger,
Probabilistically checkable proofs and their consequences for approximation algorithms
-
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
Links
