Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2006

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: number of linear extensions

Sortuj według:

Ogranicz wyniki do:

Exploiting the Lattice of Ideals Representation of a Poset

De Loof K., De Meyer H., De Baets B.

Fundamenta Informaticae

2006

Vol. 71, nr 2,3

309-321

In this paper, we demonstrate how some simple graph counting operations on the ideal lattice representation of a partially ordered set (poset) P allow for the counting of the number of linear extensions of P, for the random generation of a linear extension of P, for the calculation of the rank probabilities for every x Î P, and, finally, for the calculation of the mutual rank probabilities Prob(x > y) for every (x,y) Î P2. We show that all linear extensions can be counted and a first random linear extension can be generated in O(|I(P)|źw(P) ) time, while every subsequent random linear extension can be obtained in O( |P|źw(P)) time, where |I(P)| denotes the number of ideals of the poset P and w(P) the width of the poset P. Furthermore, we show that all rank probability distributions can be computed in O( |I(P)|źw(P)) time, while the computation of all mutual rank probabilities requires O(|I(P)|ź|P|źw(P)) time, to our knowledge the fastest exact algorithms currently known. It is well known that each of the four problems described above resides in the class of #P-complete counting problems, the counterpart of the NP-complete class for decision problems. Since recent research has indicated that the ideal lattice representation of a poset can be obtained in constant amortized time, the stated time complexity expressions also cover the time needed to construct the ideal lattice representation itself, clearly favouring the use of our approach over the standard approach consisting of the exhaustive enumeration of all linear extensions.