Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience

DOI10.1016/j.tcs.2014.04.009zbMath1417.68283OpenAlexW2020715570MaRDI QIDQ742417

David Yu Cheng Chan, David G. Kirkpatrick

Publication date: 18 September 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.04.009

zbMATH Keywords

wireless sensor networksresiliencebarrier coverageminimum colour path problems in graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (5)

On the complexity of barrier resilience for fat regions and bounded ply ⋮ Minimum cuts in geometric intersection graphs ⋮ Unnamed Item ⋮ Improved approximation bounds for the minimum constraint removal problem ⋮ How to Navigate Through Obstacles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures
• On Isolating Points Using Disks
• A threshold of ln n for approximating set cover

This page was built for publication: Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience