THE LIVING ARCHIVE

From punched cards to autonomous collaborators: the ideas, people, languages and systems that taught machines to follow—and increasingly interpret—human intent.

PAST / PRESENT / NEXT

Collection

Tag: robert-tarjan

Union-Find, Path Compression, and the Almost-Constant-Time Data Structure

Union-find evolved from early equivalence-class algorithms into one of the most efficient general-purpose data structures, with tree weighting and path compression giving sequences of set operations an inverse-Ackermann time bound.

↗

Robert Tarjan and Linear-Time Graph Algorithms: Depth-First Search as a Design Method

Robert Tarjan transformed depth-first search from a traversal routine into a design method for linear-time graph algorithms, data structures, planarity, connectivity, and set operations.

↗