On pseudo-disk hypergraphs
DOI10.1016/j.comgeo.2020.101687zbMath1470.68232arXiv1802.08799OpenAlexW3041069381MaRDI QIDQ827317
Esther Ezra, Anirudh Donakonda, Boris Aronov, Rom Pinchasi
Publication date: 7 January 2021
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.08799
planar graphsapproximation algorithmspseudo-diskshypergraphs of finite VC-dimensionminimum-weight dominating set
Hypergraphs (05C65) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved results on geometric hitting set problems
- Removing even crossings
- Dynamic connectivity for axis-parallel rectangles
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Unit disk graphs
- On the ratio of optimal integral and fractional covers
- Applications of random sampling in computational geometry. II
- Topological Hypergraphs
- Density of range capturing hypergraphs
- A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- A Greedy Heuristic for the Set-Covering Problem
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Packing and Covering with Non-Piercing Regions
- Reducibility among Combinatorial Problems
- Coloring intersection hypergraphs of pseudo-disks
- Domination in Geometric Intersection Graphs
- Toward a theory of crossing numbers
- Approximation and Online Algorithms
