Improved bounds for the binary paint shop problem

DOI10.1007/978-3-031-49193-1_16MaRDI QIDQ6591633

Robert Šámal, Pavel Valtr, Jakub Sosnovec, Jaroslav Hančl Jr., Adam Kabela, Michal Opler

Publication date: 22 August 2024

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Some heuristics for the binary paint shop problem and their expected number of colour changes
• Paintshop, odd cycles and necklace splitting
• Splitting necklaces
• Random interval graphs
• Complexity results on a paint shop problem.
• Computing solutions of the paintshop-necklace problem
• Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem
• Complexity results on restricted instances of a paint shop problem for words

This page was built for publication: Improved bounds for the binary paint shop problem