A Paint Shop Problem for Words

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


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.

Download: [img] Postscript
Download (156kB) | Preview
Download: [img] PDF
Download (159kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2000-395
Depositing User: Thomas Epping
Date Deposited: 20 Jun 2001 00:00
Last Modified: 16 Jan 2012 13:50
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/395