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 (14)

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

This page was built for publication: Complexity of barrier coverage with relocatable sensors in the plane