Termine
Beginn der Vorlesung:
16.04.2003
Beginn der Übung:
23.04.2003
| VL |
Mittwoch |
11:00 - 13:00 |
(RUD 25, 3.101) |
| Freitag |
11:00 - 13:00 |
(RUD 25, 3.101) |
| UE |
Mittwoch |
13:00 - 15:00 |
(RUD 25, 3.101) A. Taraz |
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 2002/2003 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
-
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
