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 1330 times.
    This article's PDF has been downloaded 728 times.