Geodesic
On the uniform generation of modular diagrams
The electronic journal of combinatorics, Tome 17 (2010)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
In this paper we present an algorithm that generates $k$-noncrossing, $\sigma$-modular diagrams with uniform probability. A diagram is a labeled graph of degree $\le 1$ over $n$ vertices drawn in a horizontal line with arcs $(i,j)$ in the upper half-plane. A $k$-crossing in a diagram is a set of $k$ distinct arcs $(i_1, j_1), (i_2, j_2),\ldots,(i_k, j_k)$ with the property $i_1 < i_2 < \ldots < i_k < j_1 < j_2 < \ldots < j_k$. A diagram without any $k$-crossings is called a $k$-noncrossing diagram and a stack of length $\sigma$ is a maximal sequence $((i,j),(i+1,j-1),\dots,(i+(\sigma-1),j-(\sigma-1)))$. A diagram is $\sigma$-modular if any arc is contained in a stack of length at least $\sigma$. Our algorithm generates after $O(n^k)$ preprocessing time, $k$-noncrossing, $\sigma$-modular diagrams in $O(n)$ time and space complexity.
DOI : 10.37236/447
Classification : 05A18
Mots-clés : \(k\)-noncrossing diagram, uniform generation, RSK-algorithm 
Fenix W.D. Huang; Christian M. Reidys. On the uniform generation of modular diagrams. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/447
@article{10_37236_447,
     author = {Fenix W.D. Huang and Christian M. Reidys},
     title = {On the uniform generation of modular diagrams},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/447},
     zbl = {1204.05018},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/447/}
}
TY  - JOUR
AU  - Fenix W.D. Huang
AU  - Christian M. Reidys
TI  - On the uniform generation of modular diagrams
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/447/
DO  - 10.37236/447
ID  - 10_37236_447
ER  - 
%0 Journal Article
%A Fenix W.D. Huang
%A Christian M. Reidys
%T On the uniform generation of modular diagrams
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/447/
%R 10.37236/447
%F 10_37236_447

Cité par Sources :