On the heapability of finite partial orders
From MaRDI portal
Abstract: We investigate the partitioning of partial orders into a minimal number of heapable subsets. We prove a characterization result reminiscent of the proof of Dilworth's theorem, which yields as a byproduct a flow-based algorithm for computing such a minimal decomposition. On the other hand, in the particular case of sets and sequences of intervals we prove that this minimal decomposition can be computed by a simple greedy-type algorithm. The paper ends with a couple of open problems related to the analog of the Ulam-Hammersley problem for decompositions of sets and sequences of random intervals into heapable sets.
Recommendations
- Heapability, interactive particle systems, partial orders: results and open problems
- Heapable sequences and subsequences
- Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley's process
- Almost-sure asymptotics for the number of heaps inside a random sequence
- A characterization of heaps and its applications
Cited in
(7)- The maximum binary tree problem
- Efficient methods of calculating the number of heapable permutations
- Heapability, interactive particle systems, partial orders: results and open problems
- Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley's process
- Heapable sequences and subsequences
- The Maximum Binary Tree Problem.
- Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
This page was built for publication: On the heapability of finite partial orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386613)
