Approximation algorithms for maximum independent set of pseudo-disks
From MaRDI portal
Publication:5370733
DOI10.1145/1542362.1542420zbMath1388.68285arXiv1103.1431OpenAlexW2148431844MaRDI QIDQ5370733
Timothy M. Chan, Sariel Har-Peled
Publication date: 20 October 2017
Published in: Proceedings of the twenty-fifth annual symposium on Computational geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1103.1431
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (16)
Balanced independent and dominating sets on colored interval graphs ⋮ Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve ⋮ Improved results on geometric hitting set problems ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ Geometric Packing under Nonuniform Constraints ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ Unnamed Item ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Approximation algorithms for maximum independent set of a unit disk graph ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ Limits of local search: quality and efficiency ⋮ Minimum vertex cover in rectangle graphs ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Coloring and Maximum Independent Set of Rectangles ⋮ Robust online algorithms for dynamic choosing problems
This page was built for publication: Approximation algorithms for maximum independent set of pseudo-disks
