Geodesic
Analysis of the total costs for variants of the Union-Find algorithm
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2007_special_253_a17,
     author = {Kuba, Markus and Panholzer, Alois},
     title = {Analysis of the total costs for variants of the {Union-Find} algorithm},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)},
     year = {2007},
     doi = {10.46298/dmtcs.3535},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3535/}
}
TY  - JOUR
AU  - Kuba, Markus
AU  - Panholzer, Alois
TI  - Analysis of the total costs for variants of the Union-Find algorithm
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3535/
DO  - 10.46298/dmtcs.3535
LA  - en
ID  - DMTCS_2007_special_253_a17
ER  - 
%0 Journal Article
%A Kuba, Markus
%A Panholzer, Alois
%T Analysis of the total costs for variants of the Union-Find algorithm
%J Discrete mathematics & theoretical computer science
%D 2007
%V DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3535/
%R 10.46298/dmtcs.3535
%G en
%F DMTCS_2007_special_253_a17
Kuba, Markus; Panholzer, Alois. Analysis of the total costs for variants of the Union-Find algorithm. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007). doi : 10.46298/dmtcs.3535. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3535/

Cité par Sources :