Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


Literatur für Algorithmen für Graphen



Es gibt eine Reihe von Lehrbüchern zu Algorithmen für Graphen, doch der Leser sei gewarnt, daß man eine ganze Menge über Graphen lernen muß, daß sie noch immer nicht vollständig erforscht sind, und daß sie traditionell von einem mathematischen Standpunkt aus (als Gegenstück zu einem algorithmischen Standpunkt) untersucht werden. Daher enthalten viele der Literaturstellen eine strengere und tiefgehendere Abhandlung wesentlich komplizierterer Fragen, als dies uns hier möglich ist.

Viele der Themen, die wir hier angesprochen haben, werden in den Büchern von Mehlhorn und Tarjan behandelt. Beide sind grundlegende Referenzen, die sorgfältige Darlegungen zu elementaren und weiterentwickelten Algorithmen für Graphen enthalten, mit umfangreichen Hinweisen auf neuere Literatur. Eine weitere Referenz für weiterführendes Material ist das Buch von Papadimitriou und Steiglitz. Obwohl der größte Teil des Buches wesentlich anspruchsvolleren Themen gewidmet ist (zum Beispiel enthält es eine vollständige Abhandlung zur Paarung in allgemeinen Graphen), werden in ihm viele der von uns erörterten Algorithmen behandelt, was Hinweise auf weitere Literaturstellen einschließt.

Die Anwendung der Tiefensuche auf die Lösung des Problems des Zusammenhangs von Graphen ist das Verdienst von R. E. Tarjan, dessen Originalarbeit ein gründliches Studium verdient. Die vielen Varianten von Algorithmen für das Problem der Vereinigungs-Suche aus Kapitel 30 werden von van Leeuwen und Tarjan mit Erfolg kategorisiert und verglichen. Die Algorithmen für kürzeste Pfade und minimale Spannbäume in dichten Graphen aus Kapitel 31 sind relativ alt, doch die Originalarbeiten von Dijkstra, Prim und Kruskal sind noch immer eine interessante Lektüre. Unsere Abhandlung des Problems der stabilen Ehe in Kapitel 34 beruht auf dem unterhaltsamen Vortrag von Knuth.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]