Discrete sensor placement problems in distribution networks

We consider the problem of placing sensors in a network to detect and identify thesource of any contamination. We consider two variants of this problem:

(1) sensor-constrained: we are allowed a fixed number of sensors and want to minimize contaminationdetection time; and

(2) time-constrained: we must detect contamination within a given time limit and want to minimize the number of sensors required.

Our main results are as follows. First, we give a necessary and sufficient condition for source identification.Second, we show that the sensor and time constrained versions of the problem are polynomially equivalent. Finally, we show that the sensor-constrained version of the problem is polynomially equivalent to the asymmetric k-center problem and that the time-constrained version of the problem is polynomially equivalent to the dominating set problem.