Complexity of barrier coverage with relocatable sensors in the plane

DOI10.1016/J.TCS.2015.02.006zbMATH Open1312.68212OpenAlexW2180483632MaRDI QIDQ2344757FDOQ2344757

Authors Stefan Dobrev, Stephane Durocher, Mohsen Eftekhari, Konstantinos Georgiou, Evangelos Kranakis, D. Krizanc, Lata Narayanan, Jaroslav Opatrny, J. Urrutia, Sunil 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-completenesssensor networkmobile sensorsbarrier coveragealgorithmic complexity

Mathematics Subject Classification ID

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

Recommendations

• Complexity of barrier coverage with relocatable sensors in the plane
• Barrier Coverage with Uniform Radii in 2D
• Distributed algorithms for barrier coverage using relocatable sensors

Cites work

• 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
• Maximizing barrier coverage lifetime with mobile sensors
• New Algorithms for Barrier Coverage with Mobile Sensors
• Optimal Movement of Mobile Sensors for Barrier Coverage of a Planar Region
• Optimal movement of mobile sensors for barrier coverage of a planar region

Cited in

(20)

• Optimal movement of mobile sensors for barrier coverage of a planar region
• Distributed barrier coverage with relocatable sensors
• Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots
• Barrier Coverage with Uniform Radii in 2D
• On synchronization and orientation in distributed barrier coverage with relocatable sensors
• Algorithms for the line-constrained disk coverage and related problems
• Complexity of barrier coverage with relocatable sensors in the plane
• A fast FPTAS for two dimensional barrier coverage using sink-based mobile sensors with MinSum movement
• A polynomial-time algorithm for computing the resilience of arrangements of ray sensors
• Improved PTASs for convex barrier coverage
• Approximation algorithm for MinSum linear barrier coverage with sink-based mobile sensors on the plane
• Distributed algorithms for barrier coverage using relocatable sensors
• Improved PTASs for convex barrier coverage
• Distributed algorithms for barrier coverage using relocatable sensors
• Barrier coverage with non-uniform lengths to minimize aggregate movements
• Temporal vertex cover with a sliding time window
• On time complexity for connectivity-preserving scattering of mobile robots
• Temporal vertex cover with a sliding time window
• ``Green barrier coverage with mobile sensors
• Order preserving barrier coverage with weighted sensors on a line

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

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