Markovian Network Interdiction and the Four Color Theorem

Details Markovian Network Interdiction and the Four Color Theorem Markovian Network Interdiction and the Four Color Theorem

2009-11-23

arxiv.org/abs/0911.4322v1

Computer Science

Discrete Mathematics

7 pages, 2 figures

Scientific paper

The Unreactive Markovian Evader Interdiction Problem (UME) asks to optimally place sensors on a network to detect Markovian motion by one or more "evaders". It was previously proved that finding the optimal sensor placement is NP-hard if the number of evaders is unbounded. Here we show that the problem is NP-hard with just 2 evaders using a connection to coloring of planar graphs. The results suggest that approximation algorithms are needed even in applications where the number of evaders is small. It remains an open problem to determine the complexity of the 1-evader case or to devise efficient algorithms.

Affiliated with

Also associated with

No associations

Rating

Markovian Network Interdiction and the Four Color Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Markovian Network Interdiction and the Four Color Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Markovian Network Interdiction and the Four Color Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-172873