References for Part Five

Many algorithms textbooks , including those listed below, cover many of the basic graph-processing algorithms in Chapters 17 through 21. Several of these books are basic references that give careful treatments of fundamental and advanced graph algorithms, with extensive references to the recent literature, though each book necessarily covers only a subset of the algorithms considered here.

The book by Even and the monograph by Tarjan are devoted to thorough coverage of many of the same topics that we have discussed. Tarjan's original paper on the application of depth-first search to solve strong connectivity and other problems merits further study. The source-queue topological sort implementation in Chapter 19 is from Knuth's book. Original references for some of the other specific algorithms that we have covered are listed below.

The algorithms for minimum spanning trees in dense graphs in Chapter 20 are quite old, but the original papers by Dijkstra, Prim, and Kruskal still make interesting reading. The survey by Graham and Hell provides a thorough and entertaining history of the problem. The paper by Chazelle is the state of the art in the quest for a linear MST algorithm.

The book by Ahuja, Magnanti, and Orlin is a comprehensive treatment of network-flow algorithms (and shortest-paths algorithms). Further information on nearly every topic covered in Chapters 21 and 22 may be found in that book. Another source for further material is the classic book by Papadimitriou and Steiglitz. Though most of that book is about much more advanced topics, it carefully treats many of the algorithms that we have discussed. Both books have extensive and detailed information about source material from the research literature. The classic work by Ford and Fulkerson is still worthy of study, as it introduced many of the fundamental concepts.

We have briefly introduced numerous advanced topics from (the yet to be published) Part 8, including reducibility, intractability, and linear programming, among several others. This reference list is focused on the material that we cover in detail and cannot do justice to these advanced topics. The algorithms texts treat many of them, and the book by Papadimitriou and Steiglitz provides a thorough introduction. There are numerous other books and a vast research literature on these topics.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications , Prentice Hall, 1993.

B. Chazelle, "A minimum spanning tree algorithm with inverse-Ackermann type complexity," Journal of the ACM , 47 (2000).

T. H. Cormen, C. L. Leiserson, and R. L. Rivest, Introduction to Algorithms , MIT Press and McGraw-Hill, 1990.

E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik , 1 (1959).

P. Erd s and A. Renyi, "On the evolution of random graphs," Magyar Tud. Akad. Mat. Kutato Int Kozl , 5 (1960).

S. Even, Graph Algorithms , Computer Science Press, 1979.

L. R. Ford and D. R. Fulkerson, Flows in Networks , Princeton University Press, 1962.

H. N. Gabow, " Path -based depth-first search for strong and biconnected components ," Information Processing Letters , 74 (2000).

R. L. Graham and P. Hell, "On the history of the minimum spanning tree problem," Annals of the History of Computing , 7 (1985).

D. B. Johnson, "Efficient shortest path algorithms," Journal of the ACM , 24 (1977).

D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms Third Edition , Addison-Wesley, 1997.

J. R. Kruskal Jr., "On the shortest spanning subtree of a graph and the traveling salesman problem," Proceedings AMS , 7, 1 (1956).

K. Mehlhorn, Data Structures and Algorithms 2: NP-Completeness and Graph Algorithms , Springer-Verlag, 1984.

C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity , Prentice-Hall, 1982.

R. C. Prim, "Shortest connection networks and some generalizations ," Bell System Technical Journal , 36 (1957).

R. E. Tarjan, "Depth-first search and linear graph algorithms," SIAM Journal on Computing , 1, 2 (1972).

R. E. Tarjan, Data Structures and Network Algorithms , Society for Industrial and Applied Mathematics, Philadelphia, 1983.