Line segment covering of cells in arrangements

DOI10.1016/j.ipl.2017.09.002zbMath1419.68199arXiv1708.00576OpenAlexW2755482478WikidataQ62041690 ScholiaQ62041690MaRDI QIDQ2410576

Marcel Roeloffzen, Matias Korman, Sheung-Hung Poon

Publication date: 18 October 2017

Published in: Information Processing Letters, Combinatorial Optimization and Applications (Search for Journal in Brave)

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

zbMATH Keywords

geometric graphcomputational geometryNP-hardnessvertex coverFPT

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Line segment covering of cells in arrangements, Graphs with equal domination and covering numbers, Covering and packing of rectilinear subdivision, Approximability of covering cells with line segments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Line segment covering of cells in arrangements
• A threshold of ln n for approximating set cover
• Planar Formulae and Their Uses