Complexity results on restricted instances of a paint shop problem for words

Bonsma, P. and Epping, Th. and Hochstättler, W. (2006) Complexity results on restricted instances of a paint shop problem for words. Discrete Applied Mathematics, 154 (9). pp. 1335-1343. ISSN 0166-218X

PDF
Restricted to UT campus only: Request a copy
221Kb

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 $NP$ -complete. We show that this special case is also $NP$ -complete and even $APX$ -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.
Item Type:	Article
Copyright:	© 2006 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/63734
Official URL:	http://dx.doi.org/10.1016/j.dam.2005.05.033
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 237677