Point Line Cover: The Easy Kernel is Essentially Tight

DOI10.1137/1.9781611973402.116zbMath1423.68548OpenAlexW4214909205MaRDI QIDQ5384078

Geevarghese Philip, Stefan Kratsch, Saurabh Ray

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.744.8459

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

AND-compression of NP-complete problems: streamlined proof and minor observations, Hypergraph representation via axis-aligned point-subspace cover, On the approximability of covering points by lines and related problems, Geometric hitting set for segments of few orientations