Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
From MaRDI portal
Publication:5111257
DOI10.4230/LIPIcs.MFCS.2017.42zbMath1441.68270arXiv1611.06501OpenAlexW2550398909MaRDI QIDQ5111257
Erik Jan van Leeuwen, Andreas Wiese, Michał Pilipczuk
Publication date: 26 May 2020
Full work available at URL: https://arxiv.org/abs/1611.06501
Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation algorithms for maximum independent set of pseudo-disks
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Independent Set of Convex Polygons: From $$n^{\epsilon }$$ n ϵ to $$1+\epsilon $$ 1 + ϵ via Shrinking
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
- Polynomial-time approximation schemes for packing and piercing fat objects
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
- A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
- Algorithms – ESA 2005
This page was built for publication: Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
