Approximation algorithms for maximum independent set of pseudo-disks
From MaRDI portal
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
Cites work
- scientific article; zbMATH DE number 1182757 (Why is no real title available?)
- scientific article; zbMATH DE number 1830719 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- A Separator Theorem for Planar Graphs
- A note on maximum independent sets in rectangle intersection graphs
- Almost optimal set covers in finite VC-dimension
- Applications of random sampling in computational geometry. II
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation algorithms for maximum independent set of pseudo-disks
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Computing the independence number of intersection graphs
- Dynamic Connectivity for Axis-Parallel Rectangles
- Dynamic data structures for fat objects and their applications
- Efficient approximation algorithms for tiling and packing problems with rectangles
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Graph-Theoretic Concepts in Computer Science
- Hitting sets when the VC-dimension is small
- Improved approximation algorithms for geometric set cover
- Independent set of intersection graphs of convex objects in 2D
- Label placement by maximum independent set in rectangles
- Maximum independent set of rectangles
- New existence proofs ε-nets
- On a Coloring Problem.
- On approximation properties of the independent set problem for low degree graphs
- On levels in arrangements of lines, segments, planes, and triangles
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- PTAS for geometric hitting set problems via local search
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Reporting points in halfspaces
- Simple heuristics for unit disk graphs
- State of the union (of geometric objects)
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Weighted geometric set cover via quasi-uniform sampling
Cited in
(74)- On streaming algorithms for geometric independent set and clique
- Minimum point-overlap labelling*
- Computing maximum independent set on outerstring graphs and their relatives
- scientific article; zbMATH DE number 7651162 (Why is no real title available?)
- On pseudo-disk hypergraphs
- Generalized disk graphs
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Stochastic makespan minimization in structured set systems (extended abstract)
- Geometric Packing under Nonuniform Constraints
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
- A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
- A Tight (3/2+ε) Approximation for Skewed Strip Packing.
- Approximation algorithms for polynomial-expansion and low-density graphs
- 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
- scientific article; zbMATH DE number 7378687 (Why is no real title available?)
- Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
- 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
- On the geometric priority set cover problem
- Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
- Limit theory of combinatorial optimization for random geometric graphs
- Coloring intersection hypergraphs of pseudo-disks
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Independent sets and hitting sets of bicolored rectangular families
- Approximation schemes for independent set and sparse subsets of polygons
- Shifting strategy for geometric graphs without geometry
- Simple PTAS's for families of graphs excluding a minor
- Minimum point-overlap labeling
- Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- PTASs for secure dominating set in planar graphs and growth-bounded graphs
- Local search strikes again: PTAS for variants of geometric covering and packing
- Lower bounds for piercing and coloring boxes
- Optimality of geometric local search
- Efficient independent set approximation in unit disk graphs
- On the geometric set multicover problem
- Packing and covering with balls on Busemann surfaces
- Constructing planar support for non-piercing regions
- Submodular unsplittable flow on trees
- Covering and packing of rectilinear subdivision
- Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains
- Submodular unsplittable flow on trees
- Improved algorithm for maximum independent set on unit disk graph
- Space-efficient algorithms for reachability in directed geometric graphs
- From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem
- Practical and efficient algorithms for the geometric hitting set problem
- Existence of planar support for geometric hypergraphs using elementary techniques
- On independent set in \(B_1\)-EPG graphs
- Geometric dominating-set and set-cover via local-search
- Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
- scientific article; zbMATH DE number 7236415 (Why is no real title available?)
- scientific article; zbMATH DE number 7651158 (Why is no real title available?)
- Coloring intersection hypergraphs of pseudo-disks
- Winner determination in geometrical combinatorial auctions
- Minimum vertex cover in ball graphs through local search
- Approximating dominating set on intersection graphs of rectangles and L-frames
- A note on fractional coloring and the integrality gap of LP for maximum weight independent set
- Matching colored points with rectangles
- Approximation algorithms for maximum independent set of pseudo-disks
- From a \((p,2)\)-theorem to a tight \((p,q)\)-theorem
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- Topological Drawings Meet Classical Theorems from Convex Geometry
- APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
- Maximum independent and disjoint coverage
- Anchored rectangle and square packings
- Geometric stabbing via threshold rounding and factor revealing LPs
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)
