No label defined (Q3972873)

[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.