zbMATH — the first resource for mathematics

Exploiting the lattice of ideals representation of a poset. (English) Zbl 1110.06001
The authors demonstrate how some graph counting operations on the ideal lattice representation of a poset \(P\) can be used to count the number of linear extensions of \(P\), the rank probabilities for every \(x\) of \(P\), the mutual rank probabilities Prob\((x>y)\) for every \((x,y)\) in \(P^2\), and to randomly generate a linear extension of \(P\). They establish simple and fast algorithms for generating a random linear extension and deriving (mutual) rank probabilities of a poset. Since each of the mentioned problems is known to reside in the class \(\#\text{P}\)-complete counting problems and since ideal lattice representation of a poset can be obtained in constant amortized time, the proposed approach favours the standard approach consisting in exhaustive enumeration of all linear extensions.

06A06 Partial orders, general
06A07 Combinatorics of partially ordered sets
06A05 Total orders
68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms