Dozenten: Dr. Deryk Osthus und Dirk Schlatter
Termine
Themenvergabe: 14.04.2004 (RUD 25, 3.101)Beginn des Seminars: 28.04.2004
| SE | Mittwoch | 11:00 - 13:00 | (RUD 25, 4.113) |
|---|
Zuordnung
- Hauptstudium, Seminar
Voraussetzungen
- Fundierte Kenntnisse der Theoretischen Informatik aus dem Grundstudium.
- Der Besuch von Graphen und Algorithmen 1 ist hilfreich, aber nicht notwendig.
Inhalte und Lernziele
Im Rahmen des Seminars sollen Verfahren untersucht werden, die den Knoten eines Graphen Farben so zuweisen, dass benachbarte Knoten nicht die gleiche Farbe erhalten und dabei möglichst wenig Farben verwendet werden. Diese Problemstellung findet Anwendung in vielen unterschiedlichen Bereichen, wie beispielsweise bei der Frequenzzuweisung oder bei Scheduling-Problemen. Wir werden zunächst die notwenigen Grundlagen für das Färbungsproblem erarbeiten, anschließend verschiedene algorithmische Ansätze kennenlernen, und abschließend Varianten der Problemstellung betrachten.
Empfohlene Literatur
Das Material für die Vorträge wird sich in erster Linie an Originalarbeiten anlehnen. Einen ersten Überblick findet man beispielsweise in- , Einführung in Graphen und Algorithmen (Kapitel 5)
