Seminar: Färbungsalgorithmen

Dozent: Dr. Anusch Taraz

Termine

Erste Sitzung (Vortragsvergabe): 19.04.2001

SE	Donnerstag	11:00 - 13:00	(RUD 25, 4.110)

Zuordnung

Hauptstudium, Seminar

Voraussetzungen

Fundierte Kenntnisse der Theoretischen Informatik aus dem Grundstudium

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öichst wenig Farben verwendet werden. Diese Problemstellung findet Anwendung in vielen unterschiedlichen Bereichen, wie beispielsweise bei der Register-oder Frequenzzuweisung.

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

Emden-Weinert, Hougardy, Kreuter, Prömel, Steger, Einführung in Graphen und Algorithmen

zuletzt geändert am 23.01.2006 (alkox-www)