Applications of path compression on balanced trees.

[摘要] 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.

[学科分类] 计算机科学（综合）