Efficient algorithms on distributive lattices (Q5936459): Difference between revisions

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\)).