Exploiting the Lattice of Ideals Representation of a Poset

• Autorzy: De Loof K. , De Meyer H. , De Baets B.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

poset; ideal lattice; random linear extension; number of linear extensions; rank probability distribution; mutual rank probibilities

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 71, nr 2,3
• Strony: 309--321
• Opis fizyczny: tab., bibliogr. 17 poz.

Twórcy

autor

De Loof K.

autor

De Meyer H.

autor

De Baets B.

• Department of Applied Mathematics and Computer Science Ghent University, Krijgslaan 281 S9, B-9000 Gent, Belgium,

Bibliografia

• [1] G. Brightwell and P. Winkler. Counting linear extensions. Order, 8(3):225-242, 1991.
• [2] R. Brüggemann, D. Lerche, and P.B. Sørensen. First attempts to relate structures of Hasse diagrams with mutual probabilities. Technical Report 479, The 5th workshop held at the National Environmental Research Institute (NERI), Roskilde, Denmark, 2003.
• [3] R. Bubley and M. Dyer. Faster random generation of linear extensions. Discrete Mathematics, 20:81-88, 1999.
• [4] B.A. Davey and H.A. Priestley. Introduction to Lattices and Order. Cambridge University Press, Cambridge, 2003.
• [5] M. Dyer, L.A. Goldberg, C. Greenhill, and M. Jerrum. On the relative complexity of approximate counting problems. Algorithmica, 38(3):471-500, 2003.
• [6] M. Habib, R. Medina, L. Nourine, and G. Steiner. Efficient algorithms on distributive lattices. Discrete Applied Mathematics, 110:169-187, 2001.
• [7] M. Habib and L. Nourine. Tree structure for distributive lattices and its applications. Theoretical Computer Science, 165:391-405, 1996.
• [8] Y. Koda and F. Ruskey. A gray code for the ideals of a forest poset. Journal of Algorithms, 15(2):324-340, 1993.
• [9] D. Lerche and P.B. Sørensen. Evaluation of the ranking probabilities for partial orders based on random linear extensions. Chemosphere, 53:981-992, 2004.
• [10] H. Mannila and C. Meek. Global partial orders from sequential data. Proceedings of the Sixth ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining, Boston, MA, USA, 161-168, 2000.
• [11] M. Peczarski. New results in minimum-comparison sorting. Algorithmica, 40:133-145, 2004.
• [12] G. Pruesse and F. Ruskey. Gray codes from antimatroids. Order, 10:239-252, 1993.
• [13] G. Pruesse and F. Ruskey. Generating linear extensions fast. SIAM Journal on Computing, 23:373-386, 1994.
• [14] U. Simon, R. Brüggeman, and S. Pudenz. Aspects of decision support in water management - example Berlin and Potsdam (Germany) I - spatially differentiated evaluation. Water Research, 38:1809-1816, 2004.
• [15] U. Simon, R. Brüggeman, and S. Pudenz. Aspects of decision support in water management - example Berlin and Potsdam (Germany) II - improvement of management strategies. Water Research, 38:4085-4092, 2004.
• [16] M.B. Squire. Enumerating the ideals of a poset, North Carolina State University, 1995. http://citeseer.ist.psu.edu/465417.html.
• [17] L.G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8:410-421, 1979.