{
  "id": "1706.01230",
  "version": "v1",
  "published": "2017-06-05T07:59:56.000Z",
  "updated": "2017-06-05T07:59:56.000Z",
  "title": "Computing a minimal partition of partial orders into heapable subsets",
  "authors": [
    "János Balogh",
    "Cosmin Bonchiş",
    "Diana Diniş",
    "Gabriel Istrate"
  ],
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.DS"
  ],
  "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 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-05T07:59:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A18",
      "68C05",
      "60K35"
    ],
    "keywords": [
      "partial orders",
      "heapable subsets",
      "minimal partition",
      "minimal decomposition",
      "simple greedy-type algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}