Point Line Cover

DOI10.1145/2832912zbMath1423.68547arXiv1307.2521OpenAlexW1699753700MaRDI QIDQ4962617

Saurabh Ray, Stefan Kratsch, Geevarghese Philip

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.2521

zbMATH Keywords

parameterized complexitykernelization lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} ⋮ On fair covering and hitting problems ⋮ Finding Points in General Position ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Rainbow polygons for colored point sets in the plane ⋮ Unnamed Item ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Best-case and worst-case sparsifiability of Boolean CSPs