Robert Tarjan

Princeton University

Robert Endre Tarjan is an American computer scientist at Princeton University who shared the 1986 ACM Turing Award with John Hopcroft for fundamental algorithms and data structures. Tarjan invented Tarjan's algorithm for finding strongly connected components in a directed graph in linear time, which is a cornerstone of compiler construction and software verification. He developed the splay tree (with Daniel Sleator) — a self-adjusting binary search tree with amortized O(log n) operations whose performance matches the access frequency of elements. He also invented union-find with path compression and union by rank, achieving nearly optimal efficiency for the problem and proving this through amortized analysis using the inverse Ackermann function. Tarjan's work on link-cut trees, Fibonacci heaps, and other advanced data structures has directly improved the efficiency of network flow algorithms, shortest path computations, and minimum spanning tree algorithms used in infrastructure planning, chip design, and network routing. His contributions to the analysis of algorithms established amortized complexity analysis as a standard tool.