Complexity results on restricted instances of a paint shop problem for words
From MaRDI portal
Publication:2492209
DOI10.1016/j.dam.2005.05.033zbMath1131.68048OpenAlexW2007398668MaRDI QIDQ2492209
Winfried Hochstättler, Th. Epping, Paul Bonsma
Publication date: 9 June 2006
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.033
Programming involving graphs or networks (90C35) Combinatorics on words (68R15) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (12)
Minimizing sequence-dependent setup costs in feeding batch processes under due date restrictions ⋮ Unnamed Item ⋮ Greedy colorings of words ⋮ Arc-routing for winter road maintenance ⋮ Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ Computing solutions of the paintshop-necklace problem ⋮ Some heuristics for the binary paint shop problem and their expected number of colour changes ⋮ Greedy colorings for the binary paintshop problem ⋮ Paintshop, odd cycles and necklace splitting ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ On Covering Segments with Unit Intervals
Cites Work
- Matching theory
- Decomposition of regular matroids
- Optimization, approximation, and complexity classes
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- The matroids with the max-flow min-cut property
- Complexity results on a paint shop problem.
- Some APX-completeness results for cubic graphs
- Proof verification and the hardness of approximation problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity results on restricted instances of a paint shop problem for words
