Generating a random sink-free orientation in quadratic time

Details Generating a random sink-free orientation in quadratic time Generating a random sink-free orientation in quadratic time

2001-03-27

arxiv.org/abs/math/0103189v2

Electronic Journal of Combinatorics 9 (2002), #R10

Mathematics

Probability

13 pages

Scientific paper

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/epsilon)), where m is the number of edges and epsilon 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.

Affiliated with

Also associated with

No associations

Rating

Generating a random sink-free orientation in quadratic time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generating a random sink-free orientation in quadratic time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating a random sink-free orientation in quadratic time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-659983