Efficient algorithms on distributive lattices (Q5936459): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0166-218x(00)00258-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2049890507 / rank | |||
Normal rank |
Latest revision as of 09:54, 30 July 2024
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