摘要
研究了被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况.先把该问题归结为图的顶点覆盖问题,它是一个NP完全问题；接着讨论了在网络拓扑是树的特殊情形下带权和不带权顶点覆盖问题的解,并给出了树结构上带权顶点覆盖问题的线性时间算法；然后在已有的一个近似比为2的算法基础上,结合树结构上不带权顶点覆盖问题的算法给出了图的不带权顶点覆盖问题的一个改进算法,最后用实验验证了改进算法能使观察者数目减小20%左右.
The problem that how to place the smallest observers in passive testing and assure they can monitor all the behavior of a network was studied. First the problem was modeled as an instance of vertex cover problem which was an NP-Complete problem. Then the solution to the weighted and unweighted vertex cover problem was discussed in the special case that the topology of network is a tree, and linear time algorithms for weighted vertex cover problem were proposed. Based on an existing algorithm whose approximate rate is 2, an improved algorithm for unweighted vertex cover problem on graphic topology was proposed by combining with the algorithm for unwighted vertex cover problem on tree topology, and a simulating experiment showed the improved algorithm can reduce the number of the observers by about 20%.
出处
《天津大学学报》
EI
CAS
CSCD
北大核心
2006年第7期801-805,共5页
Journal of Tianjin University(Science and Technology)
基金
国家自然科学基金重大研究计划资助项目(90104010)
国家自然科学基金(60241004)
国家973计划资助项目(2003CB314801).
关键词
被动测试
NP完全问题
近似算法
passive testing
NP-complete problem
approximation algorithm
