Output-polynomial enumeration of all fixed-cardinality ideals of a poset, respectively all fixed-cardinality subtrees of a tree.

DOI10.1007/S11083-013-9292-6MaRDI QIDQ2454050zbMATH OpenOpenAlexFDO

Authors Marcel Wild

Publication date 12 June 2014

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.2180

zbMATH Keywords

order idealsdistributive latticesWhitney numberssubtreesfixed cardinalityoutput-polynomial enumeration

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Structure and representation theory of distributive lattices (06D05)

Abstract: The N cardinality k ideals of any w-element poset (w, k variable) can be enumerated in time O(Nw^3). The corresponding bound for k-element subtrees of a w-element tree is O(Nw^5). An algorithm is described that by the use of wildcards displays all order ideals of a poset in a compact manner, i.e. not one by one.

Recommendations

• scientific article; zbMATH DE number 708774
• Efficient algorithms on distributive lattices
• A Gray Code for the Ideals of a Forest Poset
• Efficient generation of the ideals of a poset in Gray code order. II
• Calcul des idéaux d'un ordonné fini

Cites work

• scientific article; zbMATH DE number 6006014 (Why is no real title available?)
• scientific article; zbMATH DE number 108405 (Why is no real title available?)
• scientific article; zbMATH DE number 3552560 (Why is no real title available?)
• scientific article; zbMATH DE number 708774 (Why is no real title available?)
• Compactly generating all satisfying truth assignments of a Horn formula
• Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints
• Gray Codes for the Ideals of Interval Orders
• Incidence algebras that are uniquely determined by their zero-nonzero matrix pattern.
• Listing and Counting Subtrees of a Tree
• On Whitney numbers of the order ideals of generalized fences and crowns
• On estimating the number of order ideals in partial orders, with some applications
• The theory of convex geometries

Cited in

(2)

• Skyline groups are ideals. An efficient algorithm for enumerating skyline groups
• scientific article; zbMATH DE number 7666239 (Why is no real title available?)

This page was built for publication: Output-polynomial enumeration of all fixed-cardinality ideals of a poset, respectively all fixed-cardinality subtrees of a tree.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2454050)