Title of article
Complexity results on restricted instances of a paint shop problem for words Original Research Article
Author/Authors
P. Bonsma، نويسنده , , Th. Epping، نويسنده , , W. Hochst?ttler، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2006
Pages
9
From page
1335
To page
1343
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.
Keywords
NPNP-completeness , Paint shop , Sequencing , Binary matroids , MaxFlow-MinCut , APXAPX-hardness
Journal title
Discrete Applied Mathematics
Serial Year
2006
Journal title
Discrete Applied Mathematics
Record number
886284
Link To Document