Solving Some Instances of the 2-Color Problem

DOI10.1007/978-3-642-04397-0_43zbMath1261.68148OpenAlexW2170873820MaRDI QIDQ3648811

Simone Rinaldi, Stefano Brocchi, Andrea Frosini

Publication date: 1 December 2009

Published in: Discrete Geometry for Computer Imagery (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04397-0_43

zbMATH Keywords

polynomial time algorithmdiscrete tomography\(k\)-color problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computing methodologies for image processing (68U10)

Related Items (5)

New sufficient conditions on the degree sequences of uniform hypergraphs ⋮ Solving the Two Color Problem: An Heuristic Algorithm ⋮ Approximating Bicolored Images from Discrete Projections ⋮ The 1-Color Problem and the Brylawski Model ⋮ On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition

Cites Work

• Reconstruction of binary matrices under fixed size neighborhood constraints
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• On the computational complexity of determining polyatomic structures by X-rays
• Discrete tomography. Foundations, algorithms, and applications
• A solvable case of image reconstruction in discrete tomography
• Using graphs for some discrete tomography problems
• Combinatorial Properties of Matrices of Zeros and Ones
• Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms

This page was built for publication: Solving Some Instances of the 2-Color Problem