Meir & Moon [MM70] found that an average number of random cuts are necessary to destroy a random size- Cayley tree (to be compared to cuts for a linear tree). Under some probabilistic assumptions (cf. Knuth & Schönage [KS78]), the number of random cuts is distributed as the number of UNION operations experienced by a given element during the implementation of a UNION-FIND algorithm. There is also an interpretation in terms of hashing tables, that we use to obtain the limit law of .
Back to the Index