| 一类排污问题在树图上的线性算法 |
| |
| 引用本文： | 朱大铭,马绍汉. 一类排污问题在树图上的线性算法[J]. 软件学报, 1994, 5(4): 60-64 |
| |
| 作者姓名： | 朱大铭 马绍汉 |
| |
| 作者单位： | 山东大学计算机科学系，济南 250100;山东大学计算机科学系，济南 250100 |
| |
| 摘 要： | ＭＥＧＩＤＤＯ等人证明了图搜索问题的ＮＰ完全性并给出一个树图上的算法，可在Ｏ（ｎ）时间内求解树的搜索数，在Ｏ（ｎｌｏｇ（ｎ））时间内求解树搜索方案．本文通过引入搜索方案边序表示法给出一个线性算法，可在Ｏ（ｎ）时间内同时求得树的搜索数和搜索方案．
|
| 关 键 词： | 算法，NP完全性，树，无向连通图 |
| 收稿时间： | 1991-07-01 |
| 修稿时间： | 1992-01-29 |
A LINEAR ALGORITHM ON TREE FOR A CLASS OF CLEARING CONTAMINATION PROBLEMS |
| |
| Zhu Daming and Ma Shaohan. A LINEAR ALGORITHM ON TREE FOR A CLASS OF CLEARING CONTAMINATION PROBLEMS[J]. Journal of Software, 1994, 5(4): 60-64 |
| |
| Authors: | Zhu Daming and 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. |
| |
| Keywords: | Algorithm NP-complete tree undirected connected graph. |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载免费的PDF全文 |
