 |
') ;?>
') ;?>
'); ?>
In jedem Kapitel wird eine Problemklasse durch ein Beispielproblem vorgestellt. Die Praxisrelevanz der Problemklasse wird durch eine Reihe von Anwendungen motiviert. Im Anschluß werden Überlegungen vorgestellt, die zur Lösung des Problems geeignet scheinen und deren Erfolg bzw. Mißerfolg anhand der vorgestellten Probleme erläutert und begründet. Erfolgreiche Ideen werden in Algorithmen umgesetzt. Die Funktionsweise und Komplexität der Algorithmen wird im Programm verdeutlicht und dient als Motivation für den Beweis der Operationalität und die Diskussion der Komplexität im Buch.
Das Buch behandelt fünf Problemklassen. Zunächst wird das Problem, minimale aufspannende Bäume in Graphen zu finden, und seine erfolgreiche Lösung vorgestellt. Weitere Kapitel widmen sich dem Kürzeste-Wege-Problem, dem Maximaler-Fluß-Problem und dem Kardinalitätsmatching. Abschließend werden primal-duale Algorithmen zur Lösung gewichteter Matching-Probleme diskutiert.
Für die im Lehrbuch vorgestellten Algorithmen liegt eine Bibliothek von Beispielgraphen vor. Die Algorithmen zeigen auf den jeweiligen Beispielgraphen sowohl ihr typisches, aber auch ihr ,,pathologisches`` Verhalten. Der in Gato integrierten Grapheneditor erlaubt es dem Benutzer z.B. zu beobachten, inwieweit sich Änderungen der Beispielgraphen auf das Verhalten der Algorithmen auswirken.
CATBox wurde im Rahmen von Vorlesungen unserer Arbeitsgruppe Faigle/Schrader an der bzw. an der TU Cottbus erflogreich eingesetzt. Buch und Software werden im Herbst 2001 im Springer-Verlag erscheinen.
|
Kontakt: catbox@zpr.uni-koeln.de
') ;?>
') ;?>
'); ?>