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

DOI10.1016/J.TCS.2014.04.009MaRDI QIDQ742417zbMATH OpenOpenAlexFDO

Authors David Yu Cheng Chan, David 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) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms
• A Colored Path Problem and Its Applications
• scientific article; zbMATH DE number 1984545
• Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks
• Color-coding algorithms to the balanced path problem: computational issues
• Max-coloring paths: tight bounds and extensions
• Max-coloring paths: tight bounds and extensions
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• Complexity and approximation results for the min-sum and min-max disjoint paths problems

Cites work

• scientific article; zbMATH DE number 5999532 (Why is no real title available?)
• scientific article; zbMATH DE number 1445322 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures
• Introduction to algorithms
• On Isolating Points Using Disks

Cited in

(8)

• Minimum cuts in geometric intersection graphs
• On the complexity of barrier resilience for fat regions and bounded ply
• Improved approximation bounds for the minimum constraint removal problem
• Hardness of minimum barrier shrinkage and minimum installation path
• A Colored Path Problem and Its Applications
• Approximating barrier resilience for arrangements of non-identical disk sensors
• How to navigate through obstacles?
• Improved approximation bounds for the minimum constraint removal problem

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

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