Paper by Erik D. Demaine

Erik D. Demaine, Jeff Erickson, Danny Krizanc, Henk Meijer, Pat Morin, Mark Overmars, and Sue Whitesides, “Realizing Partitions Respecting Full and Partial Order Information”, Journal of Discrete Algorithms, volume 6, 2008, pages 51–58. Special issue of selected papers from the 16th Australasian Workshop on Combinatorial Algorithms, 2005.

For 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 ◇ij ℓj where ◇ij is one of <, >, or =. In the full information case, ◇ij is given for all 1 ≤ ij ≤ k. In the sequential information case, ◇ij 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 ◇1k 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.

This paper is also available from ScienceDirect.

The paper is available in PDF (171k).
See information on file formats.
[Google Scholar search]

Related papers:
Contour_AWOCA2005 (Realizing Partitions Respecting Full and Partial Order Information)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 16, 2024 by Erik Demaine.