Algorithmische Graphentheorie

Dieses Kapitel führt in die Grundbegriffe der Graphentheorie ein und beschreibt wichtige Klassen von Graphen. Es werden verschiedene Datenstrukturen für Graphen betrachtet und deren Speicherverbrauch bestimmt. Als Einführung in die algorithmische Graphentheorie wird der Algorithmus zur Bestimmung des transitiven Abschlusses eines Graphen diskutiert. Ein weiterer Abschnitt stellt Mittel zur Verfügung, um Zeit- und Platzbedarf von Algorithmen abzuschätzen und zu vergleichen. Die Beschreibung von Graphalgorithmen und deren Implementierung in einer objektorientierten Sprache werden ausführlich diskutiert. Die nachfolgenden Kapitel beschäftigen sich dann ausführlich mit weiterführenden Konzepten.

Kapitelübersicht

1. Einleitung
2. Einführung
   1. Grundlegende Definitionen
   2. Spezielle Graphen
   3. Graphalgorithmen
   4. Datenstrukturen für Graphen
   5. Der transitive Abschluss eines Graphen
   6. Vergleichskriterien für Algorithmen
   7. Implementierung von Graphalgorithmen
   8. Testen von Graph-Algorithmen
   9. Literatur
   10. Aufgaben
3. Bäume
4. Suchverfahren in Graphen
5. Entwurfsmethoden für die algorithmische Graphentheorie
6. Färbung von Graphen
7. Perfekte Graphen
8. Flüsse in Netzwerken
9. Anwendungen von Netzwerkalgorithmen
10. Kürzeste Wege
11. Approximative Algorithmen