Paintshop, odd cycles and necklace splitting

DOI10.1016/j.dam.2008.06.017zbMath1163.90774OpenAlexW2094308032MaRDI QIDQ1028475

András Sebő, Frédéric Meunier

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.06.017

zbMATH Keywords

odd cyclesMax-cutbinary clutterpaintshop problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorics on words (68R15) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Minimizing sequence-dependent setup costs in feeding batch processes under due date restrictions ⋮ Greedy colorings of words ⋮ Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem ⋮ High-multiplicity cyclic job shop scheduling ⋮ 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 ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Cites Work

• Splitting necklaces
• Matroids and multicommodity flows
• Optimization, approximation, and complexity classes
• Geometric algorithms and combinatorial optimization
• The matroids with the max-flow min-cut property
• On the complexity of the parity argument and other inefficient proofs of existence
• Complexity results on a paint shop problem.
• Some APX-completeness results for cubic graphs
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• A characterization of weakly bipartite graphs
• Complexity results on restricted instances of a paint shop problem for words
• Discrete Splittings of the Necklace
• Bisection of Circle Colorings
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Paintshop, odd cycles and necklace splitting