Some Results on a Paint Shop Problem for Words

Epping, Thomas and Hochstättler, Winfried and Oertel, Peter (2001) Some Results on a Paint Shop Problem for Words.
Published In: Electronic Notes in Discrete Mathematics 8 Elsevier 2001, pp. 31-33.


Motivated by an application in the automobile industry, we present results and conjectures on a new combinatorial problem. Given a finite alphabet B, a word w=(w_1,ldots,w_n) in B^*, a set F of colors and a coloring f=(f_1,ldots,f_n) of w, find a permutation sigma:{1,ldots,n} o {1,ldots,n} such that w_{sigma(i)}=w_i for i=1,ldots,n and the number of all color changes within sigma(f)=(f_{sigma(1)},ldots,f_{sigma(n)}) is minimized.

Download: [img] Postscript - Preprinted Version
Download (88kB) | Preview
Download: [img] PDF - Preprinted Version
Download (100kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2001-413
Depositing User: Thomas Epping
Date Deposited: 21 Nov 2001 00:00
Last Modified: 16 Jan 2012 13:12