Report Number: CS-TR-75-512
Institution: Stanford University, Department of Computer Science
Title: Applications of path compression on balanced trees.
Author: Tarjan, Robert Endre
Date: August 1975
Abstract: We devise a method for computing functions defined on paths
in trees. The method is based on tree manipulation techniques
first used for efficiently representing equivalence
relations. It has an almost-linear running time. We apply the
method to give O(m $\alpha$(m,n)) algorithms for two
A. Verifying a minimum spanning tree in an undirected graph
(best previous bound: O(m log log n) ).
B. Finding dominators in a directed graph (best previous
bound: O(n log n + m) ).
Here n is the number of vertices and m the number of edges in
the problem graph, and $\alpha$(m,n) is a very slowly growing
function which is related to a functional inverse of
The method is also useful for solving, in O(m $\alpha$(m,n))
time, certain kinds of pathfinding problems on reducible
graphs. Such problems occur in global flow analysis of
computer programs and in other contexts. A companion paper
will discuss this application.