Approximation algorithms for maximum independent set of pseudo-disks
From MaRDI portal
Publication:452004
DOI10.1007/S00454-012-9417-5zbMATH Open1248.05135OpenAlexW2077735330WikidataQ56335605 ScholiaQ56335605MaRDI QIDQ452004FDOQ452004
Authors: Timothy M. Chan, Sariel Har-Peled 
Publication date: 19 September 2012
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-012-9417-5
Recommendations
- Approximation algorithms for maximum independent set of pseudo-disks
- Approximation Algorithms for Geometric Intersection Graphs
- Efficient independent set approximation in unit disk graphs
- Graph-Theoretic Concepts in Computer Science
- Approximation schemes for independent set and sparse subsets of polygons
approximation algorithmspolynomial-time approximation schemePTASrealistic input modelsFréchet distance
Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial aspects of finite geometries (05B25)
Cites Work
- Hitting sets when the VC-dimension is small
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Applications of random sampling in computational geometry. II
- Almost optimal set covers in finite VC-dimension
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Weighted geometric set cover via quasi-uniform sampling
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- New existence proofs ε-nets
- Approximation algorithms for NP-complete problems on planar graphs
- A Separator Theorem for Planar Graphs
- Title not available (Why is that?)
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- On a Coloring Problem.
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Independent set of intersection graphs of convex objects in 2D
- On levels in arrangements of lines, segments, planes, and triangles
- Simple heuristics for unit disk graphs
- Maximum independent set of rectangles
- Polynomial-time approximation schemes for packing and piercing fat objects
- Approximation algorithms for maximum independent set of pseudo-disks
- Computing the independence number of intersection graphs
- Improved approximation algorithms for geometric set cover
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Label placement by maximum independent set in rectangles
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Dynamic data structures for fat objects and their applications
- Efficient approximation algorithms for tiling and packing problems with rectangles
- Title not available (Why is that?)
- A note on maximum independent sets in rectangle intersection graphs
- Reporting points in halfspaces
- State of the union (of geometric objects)
- On approximation properties of the independent set problem for low degree graphs
- Title not available (Why is that?)
- PTAS for geometric hitting set problems via local search
- Dynamic Connectivity for Axis-Parallel Rectangles
- Graph-Theoretic Concepts in Computer Science
Cited In (76)
- Stochastic makespan minimization in structured set systems (extended abstract)
- A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
- A Tight (3/2+ε) Approximation for Skewed Strip Packing.
- Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
- On the geometric priority set cover problem
- Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
- PTASs for secure dominating set in planar graphs and growth-bounded graphs
- Lower bounds for piercing and coloring boxes
- Covering and packing of rectilinear subdivision
- Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains
- Approximating dominating set on intersection graphs of rectangles and L-frames
- Geometric stabbing via threshold rounding and factor revealing LPs
- On streaming algorithms for geometric independent set and clique
- Minimum point-overlap labelling*
- Title not available (Why is that?)
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- On pseudo-disk hypergraphs
- Generalized disk graphs
- Geometric Packing under Nonuniform Constraints
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
- Approximation algorithms for polynomial-expansion and low-density graphs
- Title not available (Why is that?)
- Improved bounds on the Hadwiger-Debrunner numbers
- On Wegner's inequality for axis-parallel rectangles
- A tight analysis of geometric local search
- Stochastic makespan minimization in structured set systems
- Maximum area independent sets in disk intersection graphs
- Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking
- Packing and covering with non-piercing regions
- Computing inductive vertex orderings
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- A \((2+\varepsilon)\)-approximation algorithm for the storage allocation problem
- Piercing axis-parallel boxes
- Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
- Coloring intersection hypergraphs of pseudo-disks
- Approximation schemes for independent set and sparse subsets of polygons
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Limit theory of combinatorial optimization for random geometric graphs
- Independent sets and hitting sets of bicolored rectangular families
- Minimum point-overlap labeling
- Simple PTAS's for families of graphs excluding a minor
- Shifting strategy for geometric graphs without geometry
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- Conflict-free coloring of intersection graphs of geometric objects
- Local search strikes again: PTAS for variants of geometric covering and packing
- Optimality of geometric local search
- Approximability of covering cells with line segments
- Efficient independent set approximation in unit disk graphs
- Packing and covering with balls on Busemann surfaces
- On the geometric set multicover problem
- Constructing planar support for non-piercing regions
- Space-efficient algorithms for reachability in directed geometric graphs
- Submodular unsplittable flow on trees
- Submodular unsplittable flow on trees
- Improved algorithm for maximum independent set on unit disk graph
- From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem
- Geometric dominating-set and set-cover via local-search
- Existence of planar support for geometric hypergraphs using elementary techniques
- On independent set in \(B_1\)-EPG graphs
- Practical and efficient algorithms for the geometric hitting set problem
- Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
- Title not available (Why is that?)
- Title not available (Why is that?)
- Coloring intersection hypergraphs of pseudo-disks
- Minimum vertex cover in ball graphs through local search
- Winner determination in geometrical combinatorial auctions
- Approximation algorithms for maximum independent set of pseudo-disks
- From a \((p,2)\)-theorem to a tight \((p,q)\)-theorem
- A note on fractional coloring and the integrality gap of LP for maximum weight independent set
- Matching colored points with rectangles
- Topological Drawings Meet Classical Theorems from Convex Geometry
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
- Maximum independent and disjoint coverage
- Anchored rectangle and square packings
- Computing maximum independent set on outerstring graphs and their relatives
This page was built for publication: Approximation algorithms for maximum independent set of pseudo-disks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q452004)
