Geodesic
Meander Graphs
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) (2011).

Voir la notice de l'article provenant de la source Episciences

We consider a Markov chain Monte Carlo approach to the uniform sampling of meanders. Combinatorially, a meander $M = [A:B]$ is formed by two noncrossing perfect matchings, above $A$ and below $B$ the same endpoints, which form a single closed loop. We prove that meanders are connected under appropriate pairs of balanced local moves, one operating on $A$ and the other on $B$. We also prove that the subset of meanders with a fixed $B$ is connected under a suitable local move operating on an appropriately defined meandric triple in $A$. We provide diameter bounds under such moves, tight up to a (worst case) factor of two. The mixing times of the Markov chains remain open. 
@article{DMTCS_2011_special_260_a39,
     author = {Heitsch, Christine E. and Tetali, Prasad},
     title = {Meander {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)},
     year = {2011},
     doi = {10.46298/dmtcs.2926},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2926/}
}
TY  - JOUR
AU  - Heitsch, Christine E.
AU  - Tetali, Prasad
TI  - Meander Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2011
VL  - DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2926/
DO  - 10.46298/dmtcs.2926
LA  - en
ID  - DMTCS_2011_special_260_a39
ER  - 
%0 Journal Article
%A Heitsch, Christine E.
%A Tetali, Prasad
%T Meander Graphs
%J Discrete mathematics & theoretical computer science
%D 2011
%V DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2926/
%R 10.46298/dmtcs.2926
%G en
%F DMTCS_2011_special_260_a39
Heitsch, Christine E.; Tetali, Prasad. Meander Graphs. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) (2011). doi : 10.46298/dmtcs.2926. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2926/

Cité par Sources :