TY - GEN
T1 - Uniform random sampling of simple branched coverings of the sphere by itself
AU - Duchi, Enrica
AU - Poulalhon, Dominique
AU - Schaeffer, Gilles
PY - 2014/1/1
Y1 - 2014/1/1
N2 - We present the first polynomial uniform random sampling algorithm for simple branched coverings of degree n of the sphere by itself. More precisely, our algorithm generates in linear time increasing quadrangulations, which are equivalent combinatorial structures. Our result is based on the identification of some canonical labelled spanning trees, and yields a constructive proof of a celebrated formula of Hurwitz for the number of some factorizations of permutations in transpositions. The previous approaches were either non constructive or lead to exponential time algorithms for the sampling problem.
AB - We present the first polynomial uniform random sampling algorithm for simple branched coverings of degree n of the sphere by itself. More precisely, our algorithm generates in linear time increasing quadrangulations, which are equivalent combinatorial structures. Our result is based on the identification of some canonical labelled spanning trees, and yields a constructive proof of a celebrated formula of Hurwitz for the number of some factorizations of permutations in transpositions. The previous approaches were either non constructive or lead to exponential time algorithms for the sampling problem.
U2 - 10.1137/1.9781611973402.21
DO - 10.1137/1.9781611973402.21
M3 - Conference contribution
AN - SCOPUS:84902107754
SN - 9781611973389
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 294
EP - 304
BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PB - Association for Computing Machinery
T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Y2 - 5 January 2014 through 7 January 2014
ER -