Robert Tarjan

Published by Tarjan in 1972, the algorithm finds all strongly connected components (SCCs) in a directed graph in a single depth-first search pass running in O(V + E) linear time. It uses low-link values and a stack to identify maximal sets of mutually reachable vertices, and remains the standard textbook algorithm for this problem.

Splay trees, developed by Daniel Sleator and Tarjan in 1985, are self-adjusting binary search trees that move recently accessed nodes to the root through a 'splay' operation. Unlike AVL or red-black trees, they maintain no explicit balance factors, yet Sleator and Tarjan proved they achieve amortized O(log n) performance.

Tarjan shared the 1986 Turing Award with John Hopcroft for fundamental achievements in the design and analysis of algorithms and data structures. Their collaboration produced the Hopcroft-Tarjan linear-time planarity testing algorithm, and Tarjan's individual work on union-find data structures, splay trees, and graph algorithms has been foundational.

Tarjan co-developed Fibonacci heaps with Michael Fredman, which achieve optimal amortized time bounds for priority queue operations and improve the efficiency of algorithms like Dijkstra's shortest path. He also co-created link-cut trees with Sleator for dynamically maintaining forest structures, and proved tight bounds on union-find using the inverse Ackermann function.