Hardness of minimum barrier shrinkage and minimum installation path

DOI10.1016/j.tcs.2020.06.016zbMath1452.68082arXiv1910.04228OpenAlexW2979602491MaRDI QIDQ2192386

Sergio Cabello, Éric Colin de Verdière

Publication date: 17 August 2020

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

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

zbMATH Keywords

NP-hardnessactivation networkbarrier probleminstallation path

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Minimum cuts in geometric intersection graphs ⋮ Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of barrier resilience for fat regions and bounded ply
• Minimum Activation Cost Node-Disjoint Paths in Graphs with Bounded Treewidth
• Minimum Cell Connection in Line Segment Arrangements
• On Minimum Power Connectivity Problems
• Erratum
• Approximating Barrier Resilience for Arrangements of Non-identical Disk Sensors
• Minimum shared‐power edge cut

This page was built for publication: Hardness of minimum barrier shrinkage and minimum installation path