An optimal algorithm for the minimum disc cover problem

DOI10.1007/S00453-007-9043-4MaRDI QIDQ2471803zbMATH OpenOpenAlexFDO

Authors Min-Te Sun, Chih-Wei Yi, Ten H. Lai, Chuan-kai Yang

Publication date 18 February 2008

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9043-4

zbMATH Keywords

Applications in ad hoc networksMinimum disc coverOptimal algorithms

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Nonnumerical algorithms (68W05)

Recommendations

• Polynomial time approximation schemes for minimum disk cover problems
• An optimal parallel algorithm for the minimum circle-cover problem
• An exact algorithm for the maximal covering problem
• A min-cost bin covering problem and its algorithm
• An approximation algorithm for the total covering problem
• Minimum-diameter covering problems
• A note on minimum-sum coverage by aligned disks
• Algorithms for the line-constrained disk coverage and related problems
• Algorithms for the line-constrained disk coverage and related problems
• Approximation algorithms for the unit disk cover problem in 2D and 3D

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305397 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• On the complexity of computations under varying sets of primitives
• On the shape of a set of points in the plane
• The broadcast storm problem in a mobile ad hoc network

Cited in

(5)

• A note on minimum-sum coverage by aligned disks
• MINIMUM LOCAL DISK COVER SETS FOR BROADCASTING IN HETEROGENEOUS MULTIHOP WIRELESS NETWORKS
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Algorithms and Computation
• Polynomial time approximation schemes for minimum disk cover problems

This page was built for publication: An optimal algorithm for the minimum disc cover problem

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