Realizing partitions respecting full and partial order information

Erik D. Demaine, Jeff Erickson, Danny Kriz̧anc, Henk Meijer, Pat Morin, Mark Overmars, Sue Whitesides

Research output: Contribution to journalArticlepeer-review


For n ∈ N, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1, ..., ℓk such that the lengths satisfy a set of simple constraints of the form ℓi {white diamond suit}i jj where {white diamond suit}i j is one of <, >, or =. In the full information case, {white diamond suit}i j is given for all 1 ≤ i, j ≤ k. In the sequential information case, {white diamond suit}i j is given for all 1 < i < k and j = i ± 1. That is, only the relations between the lengths of consecutive intervals are specified. The cyclic information case is an extension of the sequential information case in which the relationship {white diamond suit}1 k between ℓ1 and ℓk is also given. We show that all three versions of the problem can be solved in time polynomial in k and log n.

Original languageEnglish (US)
Pages (from-to)51-58
Number of pages8
JournalJournal of Discrete Algorithms
Issue number1
StatePublished - Mar 2008


  • Integer partitions
  • Integer sequences
  • Modular arithmetic
  • Rhythm pattern
  • Rhythm perception
  • Subset-sum

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Realizing partitions respecting full and partial order information'. Together they form a unique fingerprint.

Cite this