in by factor of (mnotherssuch as [ and the graph connectivity problem in this are unaffected the paper lists examples tarjan has used path compression to obtain efficient algorithms for several graph problems [ average-case results for the union/find problem appear in [ ][ ][ ]and [ results bounding the running time of any single operation (as opposed to the entire sequenceappear in [ and [ exercise is solved in [ general union/find structuresupporting more operationsis given in [ ahoj hopcroftand ullman"on finding lowest common ancestors in trees,siam journal on computing ( ) - banachowski" complement to tarjan' result about the lower bound on the complexity of the set union problem,information processing letters ( ) - bollobas and simon"probabilistic analysis of disjoint set union algorithms,siam journal on computing ( ) - blum"on the single-operation worst-case time complexity of the disjoint set union problem,siam journal on computing ( ) - doyle and rivest"linear expected time of simple union find algorithm,information processing letters ( ) - fischer"efficiency of equivalence algorithms,in complexity of computer computation (eds miller and thatcher)plenum pressnew york - fredman and saks"the cell probe complexity of dynamic data structures,proceedings of the twenty-first annual symposium on theory of computing ( ) - gabow and tarjan" linear-time algorithm for special case of disjoint set union,journal of computer and system sciences ( ) - galler and fischer"an improved equivalence algorithm,communications of the acm ( ) - hopcroft and karp"an algorithm for testing the equivalence of finite automata,technical report tr- - department of computer sciencecornell universityithacan hopcroft and ullman"set merging algorithms,siam journal on computing ( ) - knuth and schonhage"the expected linearity of simple equivalence algorithm,theoretical computer science ( ) - lapoutre"new techniques for the union-find problem,proceedings of the first annual acm-siam symposium on discrete algorithms ( ) - lapoutre"lower bounds for the union-find and the split-find problem on pointer machines,proceedings of the twenty-second annual acm symposium on theory of computing ( ) - seidel and sharir"top-down analysis of path compression,siam journal on computing ( ) - tarjan"efficiency of good but not linear set union algorithm,journal of the acm ( ) - tarjan" class of algorithms which require nonlinear time to maintain disjoint sets,journal of computer and system sciences ( ) -