Using TPA to count linear extensions

DOI10.1016/j.jda.2018.04.001zbMath1410.68261arXiv1010.4981OpenAlexW2963807417MaRDI QIDQ1757459

Anne Perizzolo, Mark L. Huber, Jacqueline Banks, Scott M. Garrabrant

Publication date: 4 January 2019

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1010.4981

zbMATH Keywords

Monte Carloapproximation algorithmpartial ordersperfect sampling\#P-complete problems

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorics of partially ordered sets (06A07) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (3)

A Sequential Importance Sampling Algorithm for Counting Linear Extensions ⋮ A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions ⋮ A faster tree-decomposition based algorithm for counting linear extensions

Cites Work

• Unnamed Item
• Unnamed Item
• Random generation of combinatorial structures from a uniform distribution
• On the conductance of order Markov chains
• Counting linear extensions
• Faster random generation of linear extensions
• Perfect sampling using bounding chains.
• Fast perfect sampling from linear extensions
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Convex Rank Tests and Semigraphoids
• A comparative analysis of methods for constructing weak orders from partial orders
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Random Construction of Interpolating Sets for High-Dimensional Integration

This page was built for publication: Using TPA to count linear extensions