摘要
ＭＥＧＩＤＤＯ等人证明了图搜索问题的ＮＰ完全性并给出一个树图上的算法，可在Ｏ（ｎ）时间内求解树的搜索数，在Ｏ（ｎｌｏｇ（ｎ））时间内求解树搜索方案．本文通过引入搜索方案边序表示法给出一个线性算法，可在Ｏ（ｎ）时间内同时求得树的搜索数和搜索方案．
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.
出处
《软件学报》
EI
CSCD
北大核心
1994年第4期60-64,共5页
Journal of Software
关键词
树
无向连通图
线性算法
排污
Algorithm
NP-complete
tree
undirected connected graph.
