Algorithmische Graphentheorie

Die Forschung auf dem Gebiet der Informatik hat eine Reihe von allgemeinen Entwurfsmethoden für Algorithmen hervorgebracht. Viele dieser Methoden lassen sich auch beim Entwurf von Algorithmen für graphentheoretische Probleme einsetzen. Beim Entwurf neuer Algorithmen sollte zunächst die Anwendbarkeit dieser Methoden geprüft werden. In vielen Fällen wird dies schon zu Algorithmen führen, deren Laufzeit und Speicheraufwand akzeptabel sind. Zu diesen Methoden gehören die im letzten Kapitel vorgestellten Verfahren Breiten- und Tiefensuche. Dieses Kapitel stellt die Grundideen von weiteren sechs häufig angewendeten Entwurfsmethoden vor.

Kapitelübersicht

1. Einleitung
2. Einführung
3. Bäume
4. Suchverfahren in Graphen
5. Entwurfsmethoden für die algorithmische Graphentheorie
   1. Problemarten
   2. Greedy-Technik
   3. Backtracking
   4. Branch & Bound
   5. Teile & Herrsche
   6. Dynamische Programmierung
   7. Lineare Programmierung
   8. Literatur
   9. Aufgaben
6. Färbung von Graphen
7. Perfekte Graphen
8. Flüsse in Netzwerken
9. Anwendungen von Netzwerkalgorithmen
10. Kürzeste Wege
11. Approximative Algorithmen