×

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.

MSC:
06A06 Partial orders, general
06A07 Combinatorics of partially ordered sets
06A05 Total orders
68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms
PDF BibTeX XML Cite