DMTCS Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07

Font Size:  Small  Medium  Large

Analysis of the total costs for variants of the Union-Find algorithm

Markus Kuba, Alois Panholzer


We study the average behavior of variants of the Union-Find algorithm to maintain partitions of a finite set under the random spanning tree model. By applying the method of moments we can characterize the limiting distribution of the total costs of the algorithms ``Quick Find Weighted'' and ``Quick Find Biased'' extending the analysis of Knuth and Schönhage, Yao, and Chassaing and Marchand.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional