Robert (Bob) Endre Tarjan

Bob Tarjan was born on April 30, 1948 in Pomona, California. He received a B.S. in mathematics from Caltech in 1969, and was determined to do a Ph.D. but was undecided between mathematics and computer science. He finally chose computer science as a way to use his mathematical skills to solve problems of more practical interest. He entered Stanford to study artificial intelligence, but, guided by his course advisor Don Knuth, he was soon reading Volume 1 of Knuth’s The Art of Programming and studying the analysis of algorithms.

At Stanford Tarjan began a collaboration with John Hopcroft on developing efficient algorithms for graph problems. At the time there was no commonly used model for measuring efficiency analytically. Hopcroft and Tarjan decided that the model of computation would be a hypothetical computer in which the goal of the algorithm design was to minimize the worst case running time. Constant factors in the running time were ignored, so as to be machine independent. Their example problem was testing the planarity of a graph, that is, whether it can be drawn in a plane so that no edges cross.

This work led to the first linear time algorithm for planarity, which was the subject of Tarjan's Ph.D. thesis completed under the supervision of Robert W. Floyd in 1972. It emphasized depth-first search as an important algorithmic technique and advocated the use of an adjacency-list representation for sparse graphs, rather than an adjacency matrix. Other applications of the depth-first search method followed shortly, including Tarjan's linear time algorithm for finding strongly connected components. These techniques are now covered in most undergraduate courses in algorithm design. Tarjan and Hopcroft jointly received the Turing award for this and related work in 1986.

Also now part of the algorithmic canon is Tarjan's work on data structures. Tarjan realized that designing a data structure to minimize the worst case running time for each operation was unnecessarily limiting; what mattered was the total running time of the sequence of operations. Alternatively, from the point of view of the data structure, one could study the algorithm’s amortized running time, that is, its average running time per operation over a long enough sequence of inputs.

An early and well-known example of this work is Tarjan's analysis of the “union-find” data structure. [3]  The union-find problem is to maintain a collection of disjoint sets so as to efficiently perform two operations: union, which joins two sets into a single set, and find, which returns the set containing a specified element. Representing each set as a tree, two simple methods were used to give improved performance: union by weight and path compression, but their impact was not completely understood. In 1975, Tarjan was the first to analyze their combined performance exactly, showing an almost constant time per operation over long enough sequences.  This nontrivial analysis gives a time which was proportional to inverse Ackermann's function of the number of operations and elements. This was later shown to be optimal.

Tarjan held academic positions at Cornell University and then at the University of California in Berkeley before returning to Stanford University in 1974. At Stanford, Tarjan and his student Danny Sleator worked on obtaining faster solutions for the maximum flow problem by efficiently maintaining information about residual flow. They also devised the dynamic tree structure, a forest of disjoint trees in an edge-weighted graph, where trees can be split into two or linked together, and, for any path in a tree, the minimum weight edge in the path can be retrieved. Each operation runs in time which is logarithmic in the size of the tree. Underlying this data structure is a balanced ordered binary tree.

After Tarjan and Sleator moved to AT&T Bell Laboratories in 1980, they discovered a simpler means to maintain balanced binary trees, and created the “self-adjusting” binary search tree known as a splay tree. At the time, many kinds of balanced binary search trees were known which would enable lookups, inserts, deletes and other operations to be done in a worst case time which is logarithmic in the size of the tree. However maintaining these balanced trees required extra space for balance information, and complicated algorithms. The splay tree is simpler and requires no extra balance information, but has amortized running time (rather than worst case running time) which is logarithmic in the size of the tree. Whether splay trees perform as well as any binary search trees up to a constant factor is a question still unresolved. Known as the dynamic optimality conjecture, this open problem continues to inspire new research.

Tarjan's book Data Structures and Network Algorithms [6] beautifully presents his work on disjoint sets, tree data structures, minimum spanning trees, matching, and maximum flow problems. Regarded as a ``model of precision and clarity", it received the Frederick W. Lancester Prize in 1984.

Again exploiting the fact that data structures with good amortized performance would suffice, Tarjan and Michael Fredman devised the Fibonacci heap, a priority queue which implements all standard heap operations except deletion in constant amortized time. Appearing in 1985, this data structure provided significant speed-ups to several important combinatorial problems including minimum spanning tree, shortest paths, and the assignment problem.

In a seminal paper [7] in 1985, Tarjan and Sleator studied the performance of “online algorithms”, which process inputs as they happen without seeing them all at the same time, and compared them to “offline algorithms” that get to see the whole input stream at once. They introduced the notion of “competitive analysis” to rate online algorithms compared to the optimal offline algorithm, where worst-case data is imagined to be generated by an “adversary”.

They used two example problems, the list update problem and the paging problem. The list update problem is as follows: given a list of items where the cost of accessing an item is its distance from the front of the list, come up with a strategy of reordering the list so that the total cost for a sequence of access requests is minimized. Their paper shows that if each requested item is moved to the front (at constant cost) then the cost of servicing any online sequence of requests is no more than twice the cost of the optimal offline strategy that knows all future requests. The paging problem is to determine a strategy for moving pages out of cache so as to minimize the number of cache faults.

Tarjan remained at AT&T until 1989, while also serving as an adjunct professor at New York University from 1981-85. At NYU, Tarjan and his student Neal Sarnak began the first systematic study of persistent data structures—data structures which preserve the previous version of themselves when modified. This initial work resulted in a publication [11] with Jim Driscoll, Danny Sleator, and later several others with Tarjan's student Haim Kaplan at Princeton.

In 1985 Tarjan joined the faculty at Princeton University, where he is currently the James S. McDonnell Distinguished University Professor. He remained actively involved in industry at NEC Research Institute, Intertrust and the Compaq/HP Research Labs.

Tarjan returned several times to work on maximum flow and other network flow problems, with Andrew Goldberg and others. In 1995, Tarjan, with David Karger and Phil Klein, published the first linear expected time algorithm for the minimum spanning tree problem [12].

Tarjan has written over 250 papers with over 190 co-authors, and holds 15 patents. He continues to work in the area of combinatorial algorithms and data structures. In the spirit of Paul Erdös, he searches and inspires others to search for algorithms from “The Book" that records God’s best and most elegant mathematical proofs and algorithms.

Author: V. King