Approximation algorithms for maximum independent set of pseudo-disks

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

zbMATH Keywords

approximationlocal search

Mathematics Subject Classification ID

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