On the complexity of barrier resilience for fat regions and bounded ply

DOI10.1016/j.comgeo.2018.02.006zbMath1443.68204arXiv1302.4707OpenAlexW2794302811MaRDI QIDQ1615674

Maarten Löffler, Rodrigo I. Silveira, Darren Strash, Matias Korman

Publication date: 31 October 2018

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.4707

zbMATH Keywords

approximation algorithmscoverageparameterized algorithmsparameterized complexitybarrier resiliencebounded plyfat regions

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

The maximum exposure problem, Minimum cuts in geometric intersection graphs, Minimum shared‐power edge cut, Hardness of minimum barrier shrinkage and minimum installation path, How to Navigate Through Obstacles, The Maximum Exposure Problem., Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of separating points in the plane
• Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain
• Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience
• Parameterized graph separation problems
• Improved bounds on the union complexity of fat objects
• Simple and improved parameterized algorithms for multiterminal cuts
• Some simplified NP-complete graph problems
• On the boundary of the union of planar convex sets
• On the complexity of barrier resilience for fat regions
• On Isolating Points Using Disks
• Separators for sphere-packings and nearest neighbor graphs
• The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
• Multi-Commodity Network Flows