**Reference**:- Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, and Sue Whitesides, “Realizing Partitions Respecting Full and Partial Order Information”, in
*Proceedings of the 16th Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)*, Victoria, Australia, September 18–21, 2005, pages 105–114. **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*. **Length**:- The paper is 9 pages.
**Availability**:- The paper is available in PostScript (310k), gzipped PostScript (133k), and PDF (156k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- Contour_JDA (Realizing Partitions Respecting Full and Partial Order Information)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.