|
|||||
|
|
Complexity results on restricted instances of a paint shop problem for words |
|
| Authors: | P Bonsma |
| Institution: | a Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands b Department of Mathematics, BTU Cottbus, Germany c Fern Universität in Hagen, D-58084 Hagen, Germany |
| 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. |
| Keywords: | _method=retrieve& _eid=1-s2 0-S0166218X0500377X& _mathId=si4 gif& _pii=S0166218X0500377X& _issn=0166218X& _acct=C000069490& _version=1& _userid=6211566& md5=80028d0de599279b92f95bd1dee2bede')" style="cursor:pointer APX-hardness" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">APX-hardness Binary matroids MaxFlow-MinCut Paint shop _method=retrieve& _eid=1-s2 0-S0166218X0500377X& _mathId=si5 gif& _pii=S0166218X0500377X& _issn=0166218X& _acct=C000069490& _version=1& _userid=6211566& md5=8a1d8ef6eed16d94f24d8571d34a0ee9')" style="cursor:pointer NP-completeness" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">NP-completeness Sequencing |
| 本文献已被 ScienceDirect 等数据库收录！ | |