Paper by Erik D. Demaine
- 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.
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.
- The paper is 9 pages.
- 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.
These pages are generated automagically from a
Last updated January 15, 2021 by