**Reference**:- 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. **Abstract**:-
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}◇_{i j}ℓ_{j}where ◇_{i j}is one of <, >, or =. In the*full information*case, ◇_{i j}is given for all 1 ≤*i*,*j*≤*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*. **Comments**:- This paper is also available from ScienceDirect.
**Availability**:- 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.

Last updated July 23, 2024 by Erik Demaine.