Algorithmische Graphentheorie

Am Anfang der Graphentheorie standen spezifische Probleme, die leicht, d.h. ohne großen Formalismus, zu beschreiben waren. Beispiele hierfür sind das Königsberger Brückenproblem und das Vier-Farben-Problem. Während das erste Problem sich leicht lösen ließ, wurde das zweite Problem erst 1976 nach etlichen vergeblichen Anläufen gelöst. In diesem Kapitel werden Algorithmen zur Bestimmung von minimalen Eckenfärbungen vorgestellt. Da bisher kein Algorithmus mit polynomialer Laufzeit für dieses Problem bekannt ist, werden auch Heuristiken vorgestellt. Für einige spezielle Klassen von Graphen existieren effiziente Algorithmen. In diesem Kapitel werden solche Algorithmen für bipartite und planare Graphen diskutiert. Im nächsten Kapitel werden Färbungen von perfekten Graphen ausführlich behandelt. Zum Abschluss dieses Kapitels werden Färbungen von Kanten vorgestellt.

Kapitelübersicht

1. Einleitung
2. Einführung
3. Bäume
4. Suchverfahren in Graphen
5. Entwurfsmethoden für die algorithmische Graphentheorie
6. Färbung von Graphen
   1. Einführung
   2. Anwendungen von Färbungen
   3. Exakte Bestimmung der chromatischen Zahl
   4. Heuristiken zur Bestimmung von Färbungen
   5. Das Vier-Farben-Problem
   6. Kantenfärbungen
   7. Literatur
   8. Aufgaben
7. Perfekte Graphen
8. Flüsse in Netzwerken
9. Anwendungen von Netzwerkalgorithmen
10. Kürzeste Wege
11. Approximative Algorithmen