Efficient algorithms on distributive lattices (Q5936459)
From MaRDI portal
scientific article; zbMATH DE number 1613398
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient algorithms on distributive lattices |
scientific article; zbMATH DE number 1613398 |
Statements
Efficient algorithms on distributive lattices (English)
0 references
30 January 2002
0 references
This paper continues \textit{M. Habib} and \textit{L. Nourine}'s paper ``Tree structure for distributive lattices and its applications'' [Theor. Comput. Sci. 165, No. 2, 391-405 (1996; Zbl 0887.68016)], where a new representation of distributive lattices by an ideal tree was suggested. This paper gives a linear time algorithm that for an ideal tree of a distributive lattice \(L\) computes a covering relation of \(L\). Further algorithms that for a given poset \(P\) compute an ideal tree of the ideal lattice completion of \(P\) in \(O(\Delta (P)|V|)\) time and \(O (|V|)\) space (\(\Delta (P)\) is the maximum indegree in \(P\) and \(V\) is the underlying set of the ideal tree of the order lattice completion of \(P\)) and a list of all order ideals of \(P\) such that each ideal is listed twice and adjacent ideals differ in at most two vertices (so-called combinatorial Grey code \((1,2)\)) are presented. The latter algorithm needs \(O(\Delta (P)i(P))\) time and \(O(w(P)|P|)\) space (\(i(P)\) is the number of all order ideals of \(P\) and \(w(P)\) is the width of \(P\)).
0 references
poset
0 references
ideal lattice
0 references
covering relation
0 references
list of all order ideals
0 references
linear time algorithm
0 references
ideal tree
0 references