BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-75-512
       ENTRY:: August 23, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Applications of path compression on balanced trees.
        TYPE:: Technical Report
      AUTHOR:: Tarjan, Robert Endre
        DATE:: August 1975
       PAGES:: 58
    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.
       NOTES:: [Adminitrivia V1/Prg/19950823]
         END:: STAN//CS-TR-75-512