Point line cover: the easy kernel is essentially tight

DOI10.1137/1.9781611973402.116MaRDI QIDQ5384078zbMATH OpenOpenAlexFDO

Authors Stefan Kratsch, Geevarghese Philip, 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

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

Recommendations

• Point line cover: the easy kernel is essentially tight
• Reduction rules deliver efficient FPT-algorithms for covering points with lines
• Tight kernels for covering and hitting: point hyperplane cover and polynomial point hitting set
• Applications of incidence bounds in point covering problems
• A parameterized algorithm for the hyperplane-cover problem

Cited in

(6)

• Hypergraph representation via axis-aligned point-subspace cover
• Tight kernels for covering and hitting: point hyperplane cover and polynomial point hitting set
• Point line cover: the easy kernel is essentially tight
• Reduction rules deliver efficient FPT-algorithms for covering points with lines
• Hypergraph representation via axis-aligned point-subspace cover
• On the approximability of covering points by lines and related problems

This page was built for publication: Point line cover: the easy kernel is essentially tight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384078)