Entropic Uniform Sampling of Linear Extensions in Series-Parallel Posets
Résumé
In this paper, we introduce a uniform random sampler for linear extensions of Series-Parallel posets. The algorithms we present ensure an essential property of random generation algorithms: entropy. They are in a sense optimal in their consumption of random bits.