Exploiting the lattice of ideals representation of a poset. (English) Zbl 1110.06001

De Loof, Karel; De Meyer, Hans; De Baets, Bernard

Fundam. Inform. 71, No. 2-3, 309-321 (2006).

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.

Reviewer: Christoph Meinel (Potsdam)

MSC:

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

Keywords:

random linear extension; graph counting; ideal lattice representation; rank probabilities; algorithms