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 ; 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.


    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
    Funding:
      Source : OpenAIRE Graph
    • Enumeration on Graphs and Hypergraphs: Algorithms and Complexity; Funder: French National Research Agency (ANR); Code: ANR-15-CE40-0009

    Consultation statistics

    This page has been seen 1135 times.
    This article's PDF has been downloaded 639 times.