Complexity of barrier coverage with relocatable sensors in the plane

DOI10.1016/j.tcs.2015.02.006zbMath1312.68212OpenAlexW2180483632MaRDI QIDQ2344757

Stefan Dobrev, Lata Narayanan, Danny Krizanc, Konstantinos Georgiou, Jaroslav Opatrny, Evangelos Kranakis, Stephane Durocher, Jorge Urrutia, Mohsen Eftekhari, Sunil M. Shende

Publication date: 18 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.02.006

zbMATH Keywords

NP-completenessalgorithmic complexitysensor networkmobile sensorsbarrier coverage

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots, Barrier Coverage with Uniform Radii in 2D, On time complexity for connectivity-preserving scattering of mobile robots, A fast FPTAS for two dimensional barrier coverage using sink-based mobile sensors with MinSum movement, Approximation algorithm for MinSum linear barrier coverage with sink-based mobile sensors on the plane, Temporal Vertex Cover with a Sliding Time Window, Improved PTASs for convex barrier coverage, ``Green barrier coverage with mobile sensors, Algorithms for the line-constrained disk coverage and related problems, Temporal vertex cover with a sliding time window, Algorithms for covering multiple barriers, Collaborative delivery with energy-constrained mobile robots, Weak coverage of a rectangular barrier, Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements

Cites Work

• Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain
• Optimal movement of mobile sensors for barrier coverage of a planar region
• Maximizing Barrier Coverage Lifetime with Mobile Sensors
• New Algorithms for Barrier Coverage with Mobile Sensors
• Complexity of automaton identification from given data
• Complexity of Barrier Coverage with Relocatable Sensors in the Plane
• Distributed algorithms for barrier coverage using relocatable sensors
• Optimal Movement of Mobile Sensors for Barrier Coverage of a Planar Region