GENERATING A RANDOM LINEAR EXTENSION OF A PARTIAL ORDER
成果类型：
Article
署名作者：
MATTHEWS, P
刊物名称：
ANNALS OF PROBABILITY
ISSN/ISSBN：
0091-1798
DOI：
10.1214/aop/1176990349
发表日期：
1991
页码：
1367-1392
关键词：
摘要：
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.
来源URL：