Bisection of circle colorings GOLDBERG, C. H; WEST, D. B
SIAM journal on algebraic and discrete methods,
1985, 1985-01-00, 19850101, Letnik:
6, Številka:
1
Journal Article
Recenzirano
Consider $2n$ beads of $k$ colors arranged on a necklace, using $2a$, beads of color $i$. A bisection is a set of disjoint strings ("intervals") of beads whose union captures half the beads of each ...color. We prove that any arrangement with $k$ colors has a bisection using at most $\lceil k / 2 \rceil $ intervals. In addition, if $k$ is odd, an endpoint of one interval can be specified arbitrarily. The result is best possible. For fixed $k$, there is a polynomial-time algorithm to find such a bisection; it runs in $O ( n^{k - 2} )$ for $k\geqq 3$. We consider continuous and linear versions of the problem and use them to obtain applications in geometry, VLSI circuit design, and orthogonal functions.
PDF