scientific article; zbMATH DE number 16221
[For the entire collection see Zbl 0716.00004.] A linear extension (covering) of a partially ordered set \(\langle P,\leq\rangle\) is a chain \(\langle P,\sqsubseteq\rangle\) consistent with ``\(\leq\) \((x\leq y\Rightarrow x\sqsubseteq y)\). Let \(E(P)\) denote the set of all extensions of \(\langle P,\leq\rangle\) and let \(e(P)=\text{card}(E(P))\). In this paper, a dynamic programming algorithm (on the ideals of \(P\)) which finds \(e(P)\) in \({\mathcal O}(n^{k*1})\) time and \({\mathcal O}(n^ k)\) space (if \(P\) can be ``covered by \(K\)-chains) is given. It is also shown that combining dynamic programming with the decomposition approach leads to polynomial time computation of \(e(P)\) and also to \({\mathcal O}(n^ 4)\)-counting algorithms for linear extensions of trees. Some previous work of M. D. Atkinson, H. W. Chang and N. Linial is the starting point.
- Using TPA to count linear extensions
- A polynomial time algorithm for the 2-poset cover problem
- The bounds for the number of linear extensions via chain and antichain coverings
- Linear extensions of N-free orders.
- scientific article; zbMATH DE number 4041286 (Why is no real title available?)
- scientific article; zbMATH DE number 14735 (Why is no real title available?)
- Computing linear extensions for polynomial posets subject to algebraic constraints
- A faster tree-decomposition based algorithm for counting linear extensions
- Extended strict order polynomial of a poset and fixed elements of linear extensions
- Linear extensions of diamond posets
- A recurrence for linear extensions
- Counting linear extensions of posets with determinants of hook lengths
- A polynomially solvable case of optimal linear extension problem of a poset
- Loopless generation of linear extensions of a poset
- Counterexamples to conjectures about subset takeaway and counting linear extensions of a Boolean lattice
- A faster tree-decomposition based algorithm for counting linear extensions
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972873)
