Geometric dominating-set and set-cover via local-search
From MaRDI portal
Publication:6114477
DOI10.1016/j.comgeo.2023.102007arXiv1605.02499MaRDI QIDQ6114477
Publication date: 12 July 2023
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1605.02499
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Approximation algorithms for maximum independent set of pseudo-disks
- Improved results on geometric hitting set problems
- Improved approximation algorithms for geometric set cover
- The union of balls and its dual shape
- On the geometric set multicover problem
- Weighted geometric set cover via quasi-uniform sampling
- On the set multicover problem in geometric settings
- WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
- A threshold of ln n for approximating set cover
- A PTAS for the Weighted Unit Disk Cover Problem
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
- PTAS for Weighted Set Cover on Unit Squares
- Fast approximation algorithms for a nonconvex covering problem
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Reducibility among Combinatorial Problems
- On the approximability of the maximum common subgraph problem
- The Geometry of Scheduling
- Analytical approach to parallel repetition
- A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
- Domination in Geometric Intersection Graphs