A LINEAR ALGORITHM ON TREE FOR A CLASS OF CLEARING CONTAMINATION PROBLEMS
一类排污问题在树图上的线性算法

The Graph Search problem is proved to be NP-complete by MEGIDDO et al. An algorithm for tree is also proposed by them which computes the search number in O(n) time and the search plan in O (nlog (n) ) time. This paper developes a linear algorithm through representing a search plan by edge sequence, which computes both the search number and the search plan in O(n) time.