Polynomial time approximation schemes for minimum disk cover problems
From MaRDI portal
Publication:613664
DOI10.1007/S10878-009-9216-YzbMATH Open1206.90150OpenAlexW2048364862MaRDI QIDQ613664FDOQ613664
Publication date: 21 December 2010
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-009-9216-y
Recommendations
- An optimal algorithm for the minimum disc cover problem
- Approximation algorithms for the unit disk cover problem in 2D and 3D
- Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
- Combining polynomial running time and fast convergence for the disk-covering method.
- Minimum-cost coverage of point sets by disks
- scientific article; zbMATH DE number 2009908
- An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
- Approximation algorithms for partial covering problems
- A polynomial time solvable instance of the feasible minimum cover problem
- On the discrete unit disk cover problem
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
- Title not available (Why is that?)
- Unit disk graphs
- Almost optimal set covers in finite VC-dimension
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation schemes for covering and packing problems in image processing and VLSI
- The NP-completeness column: An ongoing guide
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
- Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
- Approximation schemes for wireless networks
- A better constant-factor approximation for weighted dominating set in unit disk graph
- An optimal algorithm for the minimum disc cover problem
Cited In (10)
- Approximation algorithms for the class cover problem
- Minimum constellation covers: hardness, approximability and polynomial cases
- An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
- Minimum-diameter covering problems
- Polynomial time approximation schemes for base station coverage with minimum total radii
- Online unit covering in Euclidean space
- Title not available (Why is that?)
- Multiobjective Disk Cover Admits a PTAS
- An optimal algorithm for the minimum disc cover problem
- Experiments with unit disk cover algorithms for covering massive pointsets
This page was built for publication: Polynomial time approximation schemes for minimum disk cover problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q613664)
