Merging costs for the additive Marcus-Lushnikov process, and Union-Find algorithms
Chassaing, Philippe ; Marchand, Régine
HAL, hal-00001664 / Harvested from HAL
Text on HAL
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.
Publié le : 2004-06-05
Classification:  Marcus-Lushnikov process,  additive coalescent,  parking functions,  Cayley trees,  Union-Find algorithm,  random spanning tree,  Brownian excursion,  68P10 (Primary) 60C05, 60J65, 68R05 (Secondary),  [MATH.MATH-PR]Mathematics [math]/Probability [math.PR],  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],  [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 
@article{hal-00001664,
     author = {Chassaing, Philippe and Marchand, R\'egine},
     title = {Merging costs for the additive Marcus-Lushnikov process, and Union-Find algorithms},
     journal = {HAL},
     volume = {2004},
     number = {0},
     year = {2004},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00001664}
}

Chassaing, Philippe; Marchand, Régine. Merging costs for the additive Marcus-Lushnikov process, and Union-Find algorithms. HAL, Tome 2004 (2004) no. 0, . http://gdmltest.u-ga.fr/item/hal-00001664/