Efficient algorithms on distributive lattices
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\)).
- A Gray Code for the Ideals of a Forest Poset
- A Survey of Combinatorial Gray Codes
- An algorithm to generate the ideals of a partial order
- Calcul des idéaux d'un ordonné fini
- Finding all closed sets: A general approach
- Generating Linear Extensions Fast
- Gray Codes for the Ideals of Interval Orders
- Gray codes from antimatroids
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 3204690 (Why is no real title available?)
- scientific article; zbMATH DE number 3299769 (Why is no real title available?)
- Listing and Counting Subtrees of a Tree
- Reachability analysis on distributed executions
- Tree structure for distributive lattices and its applications
- Tree structure for distributive lattices and its applications
- The stable marriage problem with restricted pairs.
- A fast algorithm for building lattices
- Representation of lattices via set-colored posets
- Skyline groups are ideals. An efficient algorithm for enumerating skyline groups
- Enumerating \(k\)-arc-connected orientations
- On random generation of fuzzy measures
- Output-polynomial enumeration of all fixed-cardinality ideals of a poset, respectively all fixed-cardinality subtrees of a tree.
- An optimal algorithm to generate tilings
- Fast Detection of Stable and Count Predicates in Parallel Computations
- scientific article; zbMATH DE number 4079486 (Why is no real title available?)
- Efficient generation of the ideals of a poset in Gray code order. II
- scientific article; zbMATH DE number 67132 (Why is no real title available?)
- scientific article; zbMATH DE number 708774 (Why is no real title available?)
- A fast incremental algorithm for building lattices
- Producing all ideals of a forest, functionally
- Central Positions in Social Networks
- Algorithms for k-meet-semidistributive lattices
- Conceptual Structures for Knowledge Creation and Communication
- Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
- Traversing combinatorial 0/1-polytopes via optimization
- Lattice structure for orientations of graphs
- Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
- Efficient polynomial algorithms for distributive lattices
- On the random generation and counting of weak order extensions of a poset with given class cardinalities
- Counting linear extension majority cycles in partially ordered sets on up to 13 elements
This page was built for publication: Efficient algorithms on distributive lattices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5936459)
