%0 Journal Article
%T A LINEAR ALGORITHM ON TREE FOR A CLASS OF CLEARING CONTAMINATION PROBLEMS<br>一类排污问题在树图上的线性算法
%A Zhu Daming
%A Ma Shaohan
%A <br>朱大铭
%A 马绍汉
%J 软件学报
%D 1994
%I 
%X 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.
%K Algorithm
%K NP-complete
%K tree
%K undirected connected graph<br>算法，NP完全性，树，无向连通图
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=F6046DDBD434E2721050E7F04630F7C6&yid=3EBE383EEA0A6494&vid=94C357A881DFC066&iid=E158A972A605785F&sid=BFE7933E5EEA150D&eid=0401E2DB1F51F8DE&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=3