Generating a Random Linear Extension of a Partial Order

Open Access
Publisher Website
Google Scholar
Abstract
Given a partial order of N items, a linear extension that is almost uniformly distributed, in the sense of variation distance, is generated. The algorithm runs in polynomial time. The technique used is a coupling for a random walk on a polygonal subset of the unit sphere in R(N). Included is a discussion of how accurately the steps of the random walk must be computed.

This publication has 0 references indexed in Scilit: