| 摘要: |
| ＭＥＧＩＤＤＯ等人证明了图搜索问题的ＮＰ完全性并给出一个树图上的算法，可在Ｏ（ｎ）时间内求解树的搜索数，在Ｏ（ｎｌｏｇ（ｎ））时间内求解树搜索方案．本文通过引入搜索方案边序表示法给出一个线性算法，可在Ｏ（ｎ）时间内同时求得树的搜索数和搜索方案． |
| 关键词: 算法，NP完全性，树，无向连通图 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| A LINEAR ALGORITHM ON TREE FOR A CLASS OF CLEARING CONTAMINATION PROBLEMS |
|
Zhu Daming,Ma Shaohan
|
| Abstract: |
| 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. |
| Key words: Algorithm NP-complete tree undirected connected graph. |
