Generating a random sink-free orientation in quadratic time
The electronic journal of combinatorics, Tome 9 (2002)
A sink-free orientation of a finite undirected graph is a choice of orientation for each edge such that every vertex has out-degree at least 1. Bubley and Dyer (1997) use Markov Chain Monte Carlo to sample approximately from the uniform distribution on sink-free orientations in time $O(m^3 \log (1 / \varepsilon))$, where $m$ is the number of edges and $\varepsilon$ the degree of approximation. Huber (1998) uses coupling from the past to obtain an exact sample in time $O(m^4)$. We present a simple randomized algorithm inspired by Wilson's cycle popping method which obtains an exact sample in mean time at most $O(nm)$, where $n$ is the number of vertices.
DOI :
10.37236/1627
Classification :
60C05, 68W20
Mots-clés : sink-free orientation, Markov chain Monte Carlo, coupling from the past, Wilson's cycle popping method
Mots-clés : sink-free orientation, Markov chain Monte Carlo, coupling from the past, Wilson's cycle popping method
@article{10_37236_1627,
author = {Henry Cohn and Robin Pemantle and James Propp},
title = {Generating a random sink-free orientation in quadratic time},
journal = {The electronic journal of combinatorics},
year = {2002},
volume = {9},
doi = {10.37236/1627},
zbl = {0994.60004},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1627/}
}
Henry Cohn; Robin Pemantle; James Propp. Generating a random sink-free orientation in quadratic time. The electronic journal of combinatorics, Tome 9 (2002). doi: 10.37236/1627
Cité par Sources :