| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420819 | Discrete Applied Mathematics | 2006 | 9 Pages |
Abstract
We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of its letters such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters.This is a special case of the paint shop problem for words, which was previously shown to be NPNP-complete. We show that this special case is also NPNP-complete and even APXAPX-hard. Furthermore, derive lower bounds for this problem and discuss a transformation into matroid theory enabling us to solve some specific instances within polynomial time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
P. Bonsma, Th. Epping, W. Hochstättler,