Computing solutions of the paintshop-necklace problem

DOI10.1016/j.cor.2012.01.014zbMath1251.90250OpenAlexW2066018442MaRDI QIDQ1761213

Bertrand Neveu, Frédéric Meunier

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2012.01.014

zbMATH Keywords

integer programmingcombinatorial optimizationlocal searchpath-following methodpaintshop problemsplitting necklaceTFNP problem

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (2)

Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Uses Software

• INCOP

Cites Work

• Some heuristics for the binary paint shop problem and their expected number of colour changes
• Necklace bisection with one cut less than needed
• Paintshop, odd cycles and necklace splitting
• Splitting necklaces
• On the complexity of the parity argument and other inefficient proofs of existence
• Complexity results on a paint shop problem.
• Greedy colorings for the binary paintshop problem
• Complexity results on restricted instances of a paint shop problem for words
• The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics
• Homotopy theory of graphs
• Combinatorial properties of certain simplicial and cubical vertex maps
• Algorithmic construction of sets for k -restrictions
• Discrete Splittings of the Necklace
• Bisection of Circle Colorings
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• The Approximation of Fixed Points of a Continuous Mapping
• Principles and Practice of Constraint Programming – CP 2004
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computing solutions of the paintshop-necklace problem