Name
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 Dilworthu0027s 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. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Combinatorics | Discrete mathematics,Combinatorics,Partition (number theory),Mathematics |
DocType | Volume | Citations |
Journal | abs/1706.01230 | 0 |
PageRank | References | Authors |
0.34 | 2 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Balogh | 1 | 113 | 9.98 |
| Cosmin Bonchiş | 2 | 13 | 7.75 |
| Diana Dinis | 3 | 0 | 0.34 |
| Gabriel Istrate | 4 | 99 | 24.96 |