Graphenalgorithmen

Originalartikel

Der Algorithmus für die Berechnung des minimalen Spannbaums stammt von R.C. Prim. Der Algorithmus für die Berechnung der kürzesten Wege geht auf E.W. Dijkstra zurück. Die Algorithmen für die Berechnung der transitiven Hülle und für alle kürzesten Wege zwischen je zwei Knoten wurden von S. Warshall und von R.W. Floyd angegeben. Die Bestimmung der Blöcke eines Graphen mithilfe der Tiefensuche stammt von J.E. Hopcroft. Pionierarbeit auf dem Gebiet der Fluss­netzwerke haben L.R. Ford und D.R. Fulkerson geleistet.

[Dij 59]   E.W. Dijkstra: A Note on two Problems in Connexion with Graphs. Numerische Mathematik 1, 269-271 (1959)

[FF 56]   L.R. Ford, D.R. Fulkerson: Maximal Flow through a Network. Canadian Journal of Mathematics 8, 399-404 (1956)

[Flo 62]   R.W. Floyd: Algorithm 97: Shortest Path. Communications of the ACM, 5, 6, 345 (1962)

[Pri 57]   R.C. Prim: Shortest Connection Networks and some Generalizations. Bell System Technical Journal, Vol. 36, 1389-1401 (1957)

[AHU 74]   A.V. Aho, J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)

[War 62]   S. Warshall: A Theorem on Boolean Matrices. Journal of the ACM, Vol. 9, 1, 11-12 (1962)

Bücher

Sehr gute Bücher speziell zum Thema Graphen­algorithmen sind die folgenden:

[Jun 94]   D. Jungnickel: Graphen, Netzwerke und Algorithmen. 3. Auflage, BI-Wissenschaftsverlag (1994)

[KN 05]   S.O. Krumke, H. Noltemeier: Graphentheoretische Konzepte und Algorithmen. Teubner (2005)

[Tur 96]   V. Turau: Algorithmische Graphentheorie. Addison-Wesley (1996)

Recht ausführliche Beschreibungen von Graphen­algorithmen finden sich auch in den folgenden Büchern:

[AHU 74]   A.V. Aho, J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)

[BB 96]   G. Brassard, P. Bratley: Fundamentals of Algorithmics. Prentice Hall (1996)

[CLRS 01]   T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)

[DMS 14]   M. Dietzfelbinger, K. Mehlhorn, P. Sanders: Algorithmen und Datenstrukturen. Springer Vieweg (2014)

[HS 81]   E. Horowitz, S. Sahni: Algorithmen. Springer (1981)

[OW 90]   T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. BI-Wissenschaftsverlag (1990)

[SW 11]   R. Sedgewick, K. Wayne: Algorithms. 4. Auflage, Addison-Wesley (2011)

[Wei 99]   M.A. Weiss: Data Structures and Algorithm Analysis in Java. Addison-Wesley (1999)

[Lan 12]   H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Die Verfahren zur Berechnung eines minimalen Spannbaums sowie zur Berechnung der transitiven Hülle und der kürzesten Wege finden Sie auch in meinem Buch über Algorithmen.
Weitere Themen des Buches: Sortieren, Textsuche, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]