Balogh, János and Bonchiş, Cosmin and Diniş, Diana and Istrate, Gabriel and Todinca, Ioan - On the heapability of finite partial orders

dmtcs:4510 - Discrete Mathematics & Theoretical Computer Science, June 29, 2020, vol. 22 no. 1 - https://doi.org/10.23638/DMTCS-22-1-17
On the heapability of finite partial orders

Authors: Balogh, János and Bonchiş, Cosmin and Diniş, Diana and Istrate, Gabriel and Todinca, Ioan

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.


Volume: vol. 22 no. 1
Section: Combinatorics
Published on: June 29, 2020
Submitted on: May 16, 2018
Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,Computer Science - Data Structures and Algorithms,05A18, 68C05, 60K35


Share

Consultation statistics

This page has been seen 197 times.
This article's PDF has been downloaded 62 times.