Philippe Chassaing: Cutting a Random Tree (and UNION-FIND Algorithms)

This is a joint work with Régine Marchand.

Meir & Moon [MM70] found that an average number $\sqrt{\pi n/2}$ of random cuts are necessary to destroy a random size-$n$ Cayley tree (to be compared to $\log n$ cuts for a linear tree). Under some probabilistic assumptions (cf. Knuth & Schönage [KS78]), the number of random cuts $X_n$ 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 $X_n/\sqrt n$.

Bibliography

CL02

Philippe Chassaing and Guy Louchard.
Phase transition for parking blocks, Brownian excursion and coalescence.
To appear in Random Structures and Algorithms, 2002.

KS78

Donald E. Knuth and Arnold Schönhage.
The expected linearity of a simple equivalence algorithm.
Theoret. Comput. Sci., 6(3):281-315, 1978.

MM70

A. Meir and J. W. Moon.
Cutting down random trees.
J. Austral. Math. Soc., 11:313-324, 1970.

Back to the Index