|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 4 van 11 gevonden artikelen
| Titel: |
Exploiting the Lattice of Ideals Representation of a Poset |
| Auteur: |
De Loof, Karel De Meyer, Hans De Baets, Bernard |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 71 (2006) nr. 2-3 pagina's 309-321 |
| Jaar: |
2006-06-15 |
| Inhoud: |
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)∈P^2. 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 ap-proach consisting of the exhaustive enumeration of all linear extensions. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 4 van 11 gevonden artikelen
| << vorige | volgende >> |