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 problems. 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 Ackermann's function. 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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/75/512/CS-TR-75-512.pdf