Network Tomography and Group Testing

Motivated by applications in network tomography, sensor networks and infection propagation, we formulate non-adaptive group testing problems on graphs. Unlike conventional group testing problems each group here must conform to the constraints imposed by a graph.

For interesting classes of graphs we arrive at a rather surprising result, namely, that the number of tests required to identify defective items is substantially similar to that required in conventional group testing problems, where no such constraints on pooling is imposed.

Network Tomography and Group Testing