Complexity of barrier coverage with relocatable sensors in the plane

DOI10.1016/J.TCS.2015.02.006MaRDI QIDQ2344757zbMATH OpenOpenAlexFDO

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

algorithmic complexitybarrier coveragemobile sensorsNP-completenesssensor network

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 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

(23)

• Optimal movement of mobile sensors for barrier coverage of a planar region
• On time complexity for connectivity-preserving scattering of mobile robots
• ``Green barrier coverage with mobile sensors
• Temporal vertex cover with a sliding time window
• 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
• Complexity of barrier coverage with relocatable sensors in the plane
• Temporal vertex cover with a sliding time window
• Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots
• Barrier Coverage with Uniform Radii in 2D
• Barrier coverage with non-uniform lengths to minimize aggregate movements
• Distributed algorithms for barrier coverage using relocatable sensors
• Distributed algorithms for barrier coverage using relocatable sensors
• A polynomial-time algorithm for computing the resilience of arrangements of ray sensors
• Distributed barrier coverage with relocatable sensors
• Improved PTASs for convex barrier coverage
• Improved PTASs for convex barrier coverage
• Algorithms for the line-constrained disk coverage and related problems
• Order preserving barrier coverage with weighted sensors on a line
• Optimal placement of mobile sensors for the distance-constrained line routing problem
• Algorithms for covering barrier points by mobile sensors with line constraint
• Drone placement for optimal barrier coverage
• On synchronization and orientation in distributed barrier coverage with relocatable sensors

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)