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

DOI10.1007/S11083-013-9292-6zbMATH Open1302.06004arXiv1208.2180OpenAlexW2145635797MaRDI QIDQ2454050FDOQ2454050

Authors: Marcel Wild 

Publication date: 12 June 2014

Published in: Order (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• The theory of convex geometries
• Title not available (Why is that?)
• Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints
• Gray Codes for the Ideals of Interval Orders
• Title not available (Why is that?)
• Compactly generating all satisfying truth assignments of a Horn formula
• Title not available (Why is that?)
• Incidence algebras that are uniquely determined by their zero-nonzero matrix pattern.
• 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
• Listing and Counting Subtrees of a Tree
• Title not available (Why is that?)

Cited In (2)

• Skyline groups are ideals. An efficient algorithm for enumerating skyline groups
• Title not available (Why is that?)

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)