Merging costs for the additive Marcus-Lushnikov process, and Union-Find algorithms

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Starting with a monodisperse configuration with $n$ size-1 particles, an additive Marcus-Lushnikov process evolves until it reaches its final state (a unique particle with mass $n$). At each of the $n-1$ steps of its evolution, a merging cost is incurred, that depends on the sizes of the two particles involved, and on an independent random factor. This paper deals with the asymptotic behaviour of the cumulated costs up to the $k$th clustering, under various regimes for $(n,k)$, with applications to the study of Union--Find algorithms.
28 pages, 1 figure

Keywords

Probability, Data Structures and Algorithms, Combinatorics, 68P10 (Primary) 60C05, 60J65, 68R05 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/71444

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0406094
 http://arxiv.org/abs/math/0406094

Collections

arXiv