Counting linear extensions
From MaRDI portal
Publication:1183942
DOI10.1007/BF00383444zbMath0759.06001WikidataQ55885264 ScholiaQ55885264MaRDI QIDQ1183942
Graham R. Brightwell, Peter M. Winkler
Publication date: 28 June 1992
Published in: Order (Search for Journal in Brave)
randomized algorithms; number of linear extensions; \(\# P\)-complete; 3-SAT Count Problem; volume of a rational polyhedron
68Q25: Analysis of algorithms and problem complexity
68R05: Combinatorics in computer science
06A07: Combinatorics of partially ordered sets
Related Items
Two Double Poset Polytopes, Why Is Pi Less Than Twice Phi?, Unnamed Item, Reconstruction of Partial Orders and List Representation as Random Structures, Upper Bounds on Mixing Time of Finite Markov Chains, The cross-product conjecture for width two posets, Sorting probability for large Young diagrams, A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions, On the Geometry of the Last Passage Percolation Problem, Preprocessing Ambiguous Imprecise Points, Unnamed Item, Approximating the volume of tropical polytopes is difficult, Polytopes and Large Counterexamples, Naruse hook formula for linear extensions of mobile posets, Counting Linear Extensions of Posets with Determinants of Hook Lengths, Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding, A Theoretical Framework for Instance Complexity of the Resource-Constrained Project Scheduling Problem, A Sequential Importance Sampling Algorithm for Counting Linear Extensions, Effective Poset Inequalities, Causal set generator and action computer, Small Complexity Gaps for Comparison-Based Sorting, Webs and posets, Universal and overlap cycles for posets, words, and juggling patterns, A comment on ``Computational complexity of stochastic programming problems, Computational complexity of a solution for directed graph cooperative games, Random threshold digraphs, On a learning precedence graph concept for the automotive industry, The combinatorics of tandem duplication, Dominance and separability in posets, their application to isoelectronic species with equal total nuclear charge, Counterexamples to conjectures about subset takeaway and counting linear extensions of a Boolean lattice, A new characterization of \(\mathcal{V} \)-posets, A faster tree-decomposition based algorithm for counting linear extensions, Similarity of personal preferences: Theoretical foundations and empirical analysis, A note on observables for counting trails and paths in graphs, On \(P\)-partitions related to ordinal sums of posets, Ehrhart polynomials of matroid polytopes and polymatroids, Flexible solutions in disjunctive scheduling: general formulation and study of the flow-shop case, Counting linear extensions, The Shapley value for cooperative games under precedence constraints, Balanced pairs in partial orders, Faster random generation of linear extensions, Order series of labelled posets, Finding parity difference by involutions, Approximating the number of linear extensions, Mixing times of lozenge tiling and card shuffling Markov chains, What is the dimension of citation space?, The computational complexity of calculating partition functions of optimal medians with Hamming distance, Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations, Crystals and trees: quasi-Kashiwara operators, monoids of binary trees, and Robinson-Schensted-type correspondences, Asymptotics of the number of standard Young tableaux of skew shape, Connected order ideals and \(P\)-partitions, Extensions of partial cyclic orders, Euler numbers and multidimensional boustrophedons, Uniquely pressable graphs: characterization, enumeration, and recognition, Using TPA to count linear extensions, Rank tests from partially ordered data using importance and MCMC sampling methods, Algorithms for computing the Shapley value of cooperative games on lattices, Counting consistent phylogenetic trees is \#P-complete, A loop-free algorithm for generating the linear extensions of a poset, Ranking the vertices of a complete multipartite paired comparison digraph, Posets with seven linear extensions sortable by three comparisons, Applying Young diagrams to 2-symmetric fuzzy measures with an application to general fuzzy measures, Entropy conservation for comparison-based algorithms, Evolution on distributive lattices, Signature cumulants, ordered partitions, and independence of stochastic processes, Hook inequalities, Counting linear extensions of restricted posets, Combinatorial Markov chains on linear extensions, On the restricted cores and the bounded core of games on distributive lattices, Bottom-up: a new algorithm to generate random linear extensions of a poset, Volume computation for sparse Boolean quadric relaxations, Fast perfect sampling from linear extensions, Sorting under partial information (without the ellipsoid algorithm)., On random generation of fuzzy measures, Linear extension numbers of \(n\)-element posets, Mixing time for Markov chain on linear extensions, The \(1/3-2/3\) Conjecture for Coxeter groups, Young tableaux with periodic walls: counting with the density method, Counting linear extensions of posets with determinants of hook lengths, Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes, Research problem: combinatorial and multilinear aspects of sign-balanced posets, On Generalized Comparison-Based Sorting Problems, Exploiting Symmetries in Polyhedral Computations, MINING POSETS FROM LINEAR ORDERS, Badness of Serial Fit Revisited, Sequence Covering Arrays and Linear Extensions, How to integrate a polynomial over a simplex, Unnamed Item, Analysis on Aggregation Function Spaces, Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
Cites Work
- The complexity of computing the permanent
- Generating a random linear extension of a partial order
- The number of depth-first searches of an ordered set
- On some complexity properties of N-free posets and posets with bounded decomposition diameter
- Computing the number of mergings with constraints
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Average height in a partially ordered set
- On the conductance of order Markov chains
- Counting linear extensions
- Balancing poset extensions
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Hard Enumeration Problems in Geometry and Combinatorics
- On the Complexity of Computing the Volume of a Polyhedron
- The Complexity of Enumeration and Reliability Problems
- A comparative analysis of methods for constructing weak orders from partial orders
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item