Complexity results on restricted instances of a paint shop problem for words

P.S. Bonsma, Th. Epping, W. Hochstättler

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)
64 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)1335-1343
Number of pages9
JournalDiscrete applied mathematics
Volume154
Issue number10/9
DOIs
Publication statusPublished - 1 Jun 2006

Keywords

  • NP-completeness
  • Paint shop
  • Sequencing
  • MaxFlow-MinCut
  • APX-hardness
  • Binary matroids

Fingerprint Dive into the research topics of 'Complexity results on restricted instances of a paint shop problem for words'. Together they form a unique fingerprint.

Cite this