On the Problem of How to Place the Observers in Passive Testing

The problem of how to place the observers in passive testing while assuring they can monitor all the behavior of a network and the number of them is the smallest is an interesting and useful problem. First, this problem is proved to be an NP-complete problem. Then a special case in which the topology of network is a tree is discussed and a linear time algorithm for it is presented. Based on the thought of tree topology an improved approximate algorithm is proposed and the approximate proportion of the improved algorithm is 2-O(1). Finally, a simulating experiment is conducted to illustrate the effectiveness of the improved algorithm and future extensions are discussed.