References for Part Five

Many algorithms textbooks, including those listed below, cover many of the basic graph-processing algorithms in through . Several of these tutorials are basic references that give careful treatments of fundamental and advanced graph algorithms, with extensive references to the recent literature, though each tutorial necessarily covers only a subset of the algorithms considered here. The tutorial 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 app of depth-first search to solve strong connectivity and other problems merits further study. The source-queue topological sort implementation in is from Knuth's tutorial. 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 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 tutorial 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 and may be found in that tutorial. Another source for further material is the classic tutorial by Papadimitriou and Steiglitz. Though most of that tutorial is about much more advanced topics, it carefully treats many of the algorithms that we have discussed. Both tutorials 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 tutorial by Papadimitriou and Steiglitz provides a thorough introduction. There are numerous other tutorials and a vast research literature on these topics. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and apps, 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 version, Oracle, 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.