Polynomial-time approximation schemes for packing and piercing fat objects

Recommendations

scientific article; zbMATH DE number 3888915
Polynomial-time approximation schemes for circle and other packing problems
Exact algorithms and APX-hardness results for geometric packing and covering problems
Approximation Schemes for Covering and Packing
Polynomial-time approximation schemes for circle packing problems

Cited in

(82)

A note on maximum independent sets in rectangle intersection graphs
An improved approximation algorithm for the discrete Fréchet distance
Anchored rectangle and square packings
Packing and covering with non-piercing regions
Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
Piercing all translates of a set of axis-parallel rectangles
Efficient independent set approximation in unit disk graphs
Consistent dynamic map labeling with fairness and importance
Range assignment of base-stations maximizing coverage area without interference
Finding, hitting and packing cycles in subexponential time on unit disk graphs
Geometric red-blue set cover for unit squares and related problems
Near-linear approximation algorithms for geometric hitting sets
Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
Independent set of intersection graphs of convex objects in 2D
Approximation algorithms on consistent dynamic map labeling
Secure connected domination and secure total domination in unit disk graphs and rectangle graphs
Improved algorithm for maximum independent set on unit disk graph
Geometric packing under non-uniform constraints
APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
Coloring and maximum independent set of rectangles
Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
PACKING A TRUCK — NOW WITH A TWIST!
On Covering Problems of Rado
Maximum area independent sets in disk intersection graphs
Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
Closest pair and the post office problem for stochastic points
A note about weak -nets for axis-parallel boxes in d-space
Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
Approximation algorithms for maximum independent set of pseudo-disks
Shifting strategy for geometric graphs without geometry
On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line
Approximation algorithms for polynomial-expansion and low-density graphs
Geometric Packing under Nonuniform Constraints
Approximation algorithms for intersection graphs
Approximation algorithms for maximum independent set of a unit disk graph
Dynamic data structures for fat objects and their applications
Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
QPTAS and subexponential algorithm for maximum clique on disk graphs
On partial covering for geometric set systems
Matching colored points with rectangles
Domination in Geometric Intersection Graphs
Minimum vertex cover in rectangle graphs
scientific article; zbMATH DE number 7053376 (Why is no real title available?)
scientific article; zbMATH DE number 7651162 (Why is no real title available?)
Parameterized complexity of geometric covering problems having conflicts
Exact and approximation algorithms for computing optimal fat decompositions
Temporal interval cliques and independent sets
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
Clique-based separators for geometric intersection graphs
Piercing all translates of a set of axis-parallel rectangles
Piercing translates and homothets of a convex body
A survey on variant domination problems in geometric intersection graphs
Maximum bipartite subgraphs of geometric intersection graphs
Online hitting set of \(d\)-dimensional fat objects
Online geometric covering and piercing
The online piercing set problem with recourse
New lower bound and algorithm for online geometric hitting set problem
Set cover, hitting set, and independent set problems for some restricted classes of geometric objects
Approximating the maximum independent set of convex polygons with a bounded number of directions
Fully dynamic maximum independent sets of disks in polylogarithmic update time
Online bichromatic piercing set problem
Maximum centre-disjoint mergeable disks
The algorithm and complexity of secure domination in 3-dimensional box graphs
Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
On the number of incidences when avoiding an induced biclique in geometric settings
Online geometric hitting set using points in \(\mathbb{Z}^d\)
Random-order online independent set of intervals and hyperrectangles
Shortest path separators in unit disk graphs
Fully dynamic maximum independent sets of disks in polylogarithmic update time
Dynamic streaming algorithms for geometric independent set
Sparse bounded hop-spanners for geometric intersection graphs
Structure and independence in hyperbolic uniform disk graphs
An O(n n) algorithm for single-source shortest paths in disk graphs
The reach of axis-aligned squares in the plane
Generalized disk graphs
A randomized algorithm for online unit clustering
Geometric representation of graphs in low dimension using axis parallel boxes
Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
Computationally-feasible truthful auctions for convex bundles
On covering problems of Rado
Approximating minimum independent dominating sets in wireless networks

This page was built for publication: Polynomial-time approximation schemes for packing and piercing fat objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4808318)