A.M. TURING AWARD WINNERS BY...

Robert (Bob) Endre Tarjan DL Author Profile link

United States – 1986
Short Annotated Bibliography
  1. Tarjan, R. E., “Depth-First Search and Linear Graph Algorithms,” SIAM Journal of Computing, Vol. 1, Num. 2, pp. 146-160, June 1972. This paper demonstrates the usefulness of depth-first search in finding biconnected components of an undirected graph and strongly connected components of a directed graph.
  2. Hopcroft, J. E. and R. E. Tarjan, “Efficient Planarity Testing,” Journal of the ACM, Vol. 21, No. 4, pp. 549-568, October, 1974.  Available here. This paper gives a linear time algorithm to test if a graph is planar.
  3. Tarjan, R. E., “Efficiency of a Good But Not Linear Set Union Algorithm,” Journal of the ACM, Vol. 22, Num. 2, pp. 215-225, April 1975. Available here.This presents the analysis of the union-find data structure for maintaining disjoint sets in amortized time proportional to inverse Ackermann's function of the number of operations and number of elements.
  4. Lipton, R. J. and R. E. Tarjan, “A separator theorem for planar graphs,” SIAM Journal on Applied Mathematics, Vol. 36, Num. 2, pp. 177-89, 1979. This paper gives a linear time algorithm to find a small set of vertices in a planar graph whose removal separates the graph into two components of similar size.
  5. Sleator, D. D. and R. E. Tarjan, “A Data Structure for Dynamic Trees,” Journal of Computer System Science, Vol. 26, Num. 3, pp. 362-391, June 1983.  Given a graph with edge weights, the dynamic tree data structure maintains a vertex-disjoint forest of trees under link and cut operations, so that the minimum cost edge on any path in a tree can be found in a time per operation which is logarithmic in the size of the tree. Applications to the lowest common ancestor and maximum flow problems are shown.
  6. Tarjan, R. E., Data structures and network algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, 1983. This monograph clearly and concisely describes Tarjan's work on data structures (disjoint sets, heaps, splay trees, and dynamic trees) and their applications to minimum spanning tree, shortest paths, network flows and matching problems.
  7. Sleator, D. D. and R. E. Tarjan, “Amortized Efficiency of List Update and Paging Rules,” Communications of the ACM, Vol. 28, Num. 2, pp. 202-208, February 1985. Available here.This paper introduces the question of online competitive analysis and analyzes a simple list update problem and the performance of paging rules for caches in that model.
  8. Sleator, D. D. and R. E. Tarjan, “Self-Adjusting Binary Search Trees,” Journal of the ACM, Vol. 32, Num. 3, pp. 652-686, July 1985. Available here.In this paper the splay tree data structure is introduced. It matches the performance of a balanced binary search tree (in the amortized sense) but requires no storage of balance information and is simpler.
  9. Fredman, M. L. and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” Journal of the ACM, Vol. 34, Num. 3, pp. 596-615, July 1987. Available here. A variant of a heap is shown to have amortized constant cost for all standard heap operations except extract minimum, which requires logarithmic time. Improvements to single-source shortest path, all-pairs shortest path, weighted bipartite matching, and the minimum spanning tree problems are shown.
  10. Goldberg, A. V. and R. E. Tarjan, “A new approach to the maximum-flow problem,” Journal of the ACM, Vol. 35, Num. 4, pp. 921-940, October 1988. Available here.
  11. Driscoll, J. R., N. Sarnak, D. D. Sleator and Robert Endre Tarjan, “Making data structures persistent.” Journal of Computer Systems Science, Vol. 38, No. 1, pp. 86-124, February 1989.  Persistent data structures perform updates while maintaining access to old versions. This paper introduces a systematic study of this topic, and considers linked lists and binary search trees.
  12. Karger, D. R., P. N. Klein and R. E. Tarjan, “A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees,” Journal of the ACM, Vol. 42, Num. 2, pp. 321-328, March 1995. Available here.