Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction

DOI10.4086/CJTCS.2014.003MaRDI QIDQ3191146zbMATH OpenOpenAlexFDO

Authors Mark Huber

Publication date 24 September 2014

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/cjtcs.2014.003

zbMATH Keywords

corrugated surfaceslinear extensionsperfect simulation

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Generating Linear Extensions Fast
• Faster random generation of linear extensions
• Counting linear extensions
• Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets
• Fast perfect sampling from linear extensions

Cites work

• Counting linear extensions
• Fast perfect sampling from linear extensions
• Faster random generation of linear extensions
• Generating a random linear extension of a partial order
• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 6416732 (Why is no real title available?)
• Mixing times of lozenge tiling and card shuffling Markov chains
• On the conductance of order Markov chains

Cited in

(3)

• Counting linear extensions of restricted posets
• Bottom-up: a new algorithm to generate random linear extensions of a poset
• Fast perfect sampling from linear extensions

This page was built for publication: Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191146)