A class of algorithms which require nonlinear time to maintain disjoint sets

The Design and Analysis of Computer Algorithms

1974 • 9,688 citations

Complexity of Computer Computations

1972 • 2,804 citations

The Art of Computer Programming

1968 • 1,671 citations

Efficiency of a Good But Not Linear Set Union Algorithm

1975 • 1,348 citations

The equivalence problem for regular expressions with squaring requires exponential space

1972 • 620 citations

THE COMPUTATIONAL COMPLEXITY OF ALGEBRAIC AND NUMERIC PROBLEMS.

1975 • 409 citations

Super-Exponential Complexity of Presburger Arithmetic

1998 • 335 citations

Applications of Path Compression on Balanced Trees

1979 • 300 citations

An improved equivalence algorithm

1964 • 284 citations

On recognizing graph properties from adjacency matrices

1976 • 186 citations

Set Merging Algorithms

1973 • 177 citations

The intrinsically exponential complexity of the circularity problem for attribute grammars

1975 • 118 citations

The expected linearity of a simple equivalence algorithm

1978 • 86 citations

Efficiency of Equivalence Algorithms

1972 • 52 citations

Linear expected time of a simple union-find algorithm

1976 • 37 citations

Solving path problems on directed graphs.

1975 • 25 citations

REAL-TIME SIMULATION OF MULTIDIMENSIONAL TURING MACHINES BY STORAGE MODIFICATION MACHINES

1973 • 19 citations