| Generating a Random Sink-Free Orientation (2007) | |||||||||||||||
Abstract | |||||||||||||||
| A sink-free orientation of a nite 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 of edges and " the degree of approximation. Huber (1998) uses coupling from the past to obtain an exact sample in time O(m ). 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. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||