Graphs, Networks and Algorithms
Dieter Jungnickel
Springer, Berlin, pp. 589, 1999, 69,95 €
ISBN 978-3-642-32278-5
Das vorliegende Buch erschien nun als fünftes der Springer-Reihe Algorithms and Computation in Mathematics, welche von E. Becker, M. Bronstein, H. Cohen, D. Eisenbud und R. Gilman herausgegeben wird. Allerdings handelt es sich hierbei nicht um ein gänzlich neues Buch, sondern im wesenlichen um eine englische Übersetzung der dritten Auflage (1994) des in deutscher Sprache bei BI (inzwischen: Spektrum Akademischer Verlag) erschienenen Buchs Graphen, Netzwerke und Algorithmen.
Von einem algorithmischen Standpunkt aus gibt Graphs, Networks and Algorithms eine Einführung in die Grundbegriffe der Graphentheorie und der graphentheoretisch formulierbaren Probleme der kombinatorischen Optimierung. Jeder Algorithmus wird in Pseudo-Code dargestellt und auf seine asymptotische Komplexität hin untersucht. Der Autor macht klar, daß eine Komplexitätsanalyse von den verwendeten Datenstrukturen abhängig ist und bezieht diese immer in seine Ausführungen mit ein.
Die folgenden Themen werden behandelt: Kürzeste Wege, aufspannende Bäume, Greedy-Algorith-men, Flüsse, bipartite Graphen, Zirkulationen, Färbungen, Zusammenhangsfragen und Matchings. Das letzte Kapitel behandelt dann schließlich als typisches NP-vollständiges Problem das TSP (Traveling Salesman Problem = Problem des Handlungsreisenden). Hier werden sowohl praktikable Algorithmen zur Auffindung der besten Tour als auch solche zur Bestimmung guter Näherungslösungen diskutiert.
Das Buch enthält Lösungshinweise zu den zahlreichen Übungsaufgaben und einen ausführlichen Index. Es sollte (in der deutschen oder in der englischen Fassung) in keiner Bücherei fehlen.
Rezension: Wolfram Koepf (Leipzig) aus Computeralgebra-Rundbrief, Nr. 25 - Oktober 1999