János Balogh ; Cosmin Bonchiş ; Diana Diniş ; Gabriel Istrate ; Ioan Todinca - 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 ordersArticle

Authors: János Balogh ORCID; Cosmin Bonchiş ; Diana Diniş ; Gabriel Istrate ; Ioan Todinca

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.

https://doi.org/10.23638/DMTCS-22-1-17
Source: arXiv.org:1706.01230
Volume: vol. 22 no. 1
Section: Combinatorics
Published on: June 29, 2020
Accepted on: May 12, 2020
Submitted on: May 16, 2018
Keywords: Mathematics - Combinatorics, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, 05A18, 68C05, 60K35
Licence: arXiv.org - Non-exclusive license to distribute
Funding:
    Source : OpenAIRE Graph
  • Enumeration on Graphs and Hypergraphs: Algorithms and Complexity; Funder: French National Research Agency (ANR); Code: ANR-15-CE40-0009

Classifications

Mathematics Subject Classification 20201
Sources:
  • [1] zbMATH Open.

Share and export

Consultation statistics

This page has been seen 1904 times.
This article's PDF has been downloaded 1161 times.