Epping, Thomas and Hochstättler, Winfried and Oertel, Peter (2000) A Paint Shop Problem for Words.
Technical Report , 7 p.

Abstract

Motivated by an application in the automobile industry, we present results on the following problem: Given a word w=(w_1,ldots,w_n) and a color vector f=(f_1,ldots,f_n) with f_i denoting the color of w_i, find a permutation sigma in mathcal{S}_n such that w_{sigma(i)}=w_i and the number of color changes within sigma(f)=(f_{sigma(1)},ldots,f_{sigma(n)}) is minimized. We show that this problem is polynomially solvable if we bound both, the number of letters and the number of colors, and becomes NP-complete otherwise.

Actions:

Download:	Postscript Download (156kB) | Preview
Download:	PDF Download (159kB) | Preview
Editorial actions:	View Item (Login required)