Geodesic
On the uniform generation of modular diagrams
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
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

Cité par Sources :