Covering and packing of rectilinear subdivision

DOI10.1016/j.tcs.2020.07.038zbMath1455.68231arXiv1809.07214MaRDI QIDQ5918965

Supantha Pandit, Satyabrata Jana

Publication date: 17 September 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

independent set; dominating set; NP-hardness; PTAS; set cover; planar subdivision

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms