Faster random generation of linear extensions

DOI10.1016/S0012-365X(98)00333-1zbMath0934.65005WikidataQ29303267 ScholiaQ29303267MaRDI QIDQ1301730

Russ Bubley, Martin Dyer

Publication date: 27 April 2000

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Markov chainsalmost uniform samplingKarzanov-Khachiyan chainsrandom generation of linear extensionstheory of approximate sampling

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Markov processes: estimation; hidden Markov models (62M05) Continuous-time Markov processes on general state spaces (60J25) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Numerical analysis or methods applied to Markov chains (65C40)

Related Items

Fast perfect sampling from linear extensions, Upper Bounds on Mixing Time of Finite Markov Chains, Complexity reduction and approximation of multidomain systems of partially ordered data, On the random generation and counting of weak order extensions of a poset with given class cardinalities, Deterministic Random Walks for Rapidly Mixing Chains, A Sequential Importance Sampling Algorithm for Counting Linear Extensions, Bijecting hidden symmetries for skew staircase shapes, Mixing time for Markov chain on linear extensions, Spectral Gap for Random-to-Random Shuffling on Linear Extensions, On random generation of fuzzy measures, Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets, Counting linear extensions: parameterizations by treewidth, Combinatorial Markov chains on linear extensions, Constraining strong \(c\)-Wilf equivalence using cluster poset asymptotics, Using TPA to count linear extensions, On the random generation of monotone data sets, Bottom-up: a new algorithm to generate random linear extensions of a poset, Rank tests from partially ordered data using importance and MCMC sampling methods, Algorithms for computing the Shapley value of cooperative games on lattices, Convergence rates of Markov chains for some self-assembly and non-saturated Ising models, Unnamed Item, Sampling biased monotonic surfaces using exponential metrics, Linear Extension Diameter of Downset Lattices of 2-Dimensional Posets, Balanced pairs in partial orders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating a random linear extension of a partial order
• Approximate counting, uniform generation and rapidly mixing Markov chains
• On the conductance of order Markov chains
• Counting linear extensions
• Generating a random permutation with random transpositions
• Generating Linear Extensions Fast
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• On Markov Chains for Independent Sets