Geodesic
Mixing times of Markov chains on 3-Orientations of Planar Triangulations
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012).

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

Given a planar triangulation, a 3-orientation is an orientation of the internal edges so all internal vertices have out-degree three. Each 3-orientation gives rise to a unique edge coloring known as a $\textit{Schnyder wood}$ that has proven useful for various computing and combinatorics applications. We consider natural Markov chains for sampling uniformly from the set of 3-orientations. First, we study a "triangle-reversing'' chain on the space of 3-orientations of a fixed triangulation that reverses the orientation of the edges around a triangle in each move. We show that (i) when restricted to planar triangulations of maximum degree six, the Markov chain is rapidly mixing, and (ii) there exists a triangulation with high degree on which this Markov chain mixes slowly. Next, we consider an "edge-flipping'' chain on the larger state space consisting of 3-orientations of all planar triangulations on a fixed number of vertices. It was also shown previously that this chain connects the state space and we prove that the chain is always rapidly mixing. 
@article{DMTCS_2012_special_262_a31,
     author = {Miracle, Sarah and Randall, Dana and Streib, Amanda Pascoe and Tetali, Prasad},
     title = {Mixing times of {Markov} chains on {3-Orientations} of {Planar} {Triangulations}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)},
     year = {2012},
     doi = {10.46298/dmtcs.3010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3010/}
}
TY  - JOUR
AU  - Miracle, Sarah
AU  - Randall, Dana
AU  - Streib, Amanda Pascoe
AU  - Tetali, Prasad
TI  - Mixing times of Markov chains on 3-Orientations of Planar Triangulations
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3010/
DO  - 10.46298/dmtcs.3010
LA  - en
ID  - DMTCS_2012_special_262_a31
ER  - 
%0 Journal Article
%A Miracle, Sarah
%A Randall, Dana
%A Streib, Amanda Pascoe
%A Tetali, Prasad
%T Mixing times of Markov chains on 3-Orientations of Planar Triangulations
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3010/
%R 10.46298/dmtcs.3010
%G en
%F DMTCS_2012_special_262_a31
Miracle, Sarah; Randall, Dana; Streib, Amanda Pascoe; Tetali, Prasad. Mixing times of Markov chains on 3-Orientations of Planar Triangulations. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012). doi : 10.46298/dmtcs.3010. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3010/

Cité par Sources :