Identifying defective network components through restricted group testing

Abstract

In this paper, we consider a network of switches in which some of the switches may malfunction. Our aim is to fnd out efciently (a) if any of the switches in a network of switches are defective, and (b) if there are defective switches, to identify those switches. We fnd an optimal solution for the frst problem and a heuristic solution to the second, and demonstrate the feasibility of our approach through computational experiments.