Selecting and covering colored points
From MaRDI portal
Publication:1801049
DOI10.1016/j.dam.2018.05.011zbMath1398.05212OpenAlexW2805761617WikidataQ129752016 ScholiaQ129752016MaRDI QIDQ1801049
Marina Simakov, Joseph S. B. Mitchell, Esther M. Arkin, Aritra Banik, Matthew J. Katz, Gui Citovsky, Paz Carmi
Publication date: 26 October 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2018.05.011
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Ramsey theory (05D10)
Related Items
Fréchet Distance for Uncertain Curves ⋮ Improved and generalized algorithms for burning a planar point set ⋮ Exact and heuristic methods for a workload allocation problem with chain precedence constraints ⋮ Unnamed Item ⋮ Covering segments with unit squares ⋮ Parameterized complexity of conflict-free set cover ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ On Covering Segments with Unit Intervals
Cites Work
- Unnamed Item
- Unnamed Item
- Nested satisfiability
- Approximating the tree and tour covers of a graph
- A simplified NP-complete satisfiability problem
- A dichotomy theorem for maximum generalized satisfiability problems.
- Optimal packing and covering in the plane are NP-complete
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- The hidden algorithm of Ore's theorem on Hamiltonian cycles
- Bichromatic 2-center of pairs of points
- The Approximability of Constraint Satisfaction Problems
- The Approximability of the Binary Paintshop Problem
- Geometric Avatar Problems
- Note on Hamilton Circuits
- Choice Is Hard
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Planar Formulae and Their Uses
- On alternativep-center problems
- Some Matching Problems for Bipartite Graphs
- Minimum-diameter covering problems
- The complexity of theorem-proving procedures
- Some Theorems on Abstract Graphs
