| 被动测试中网络监测问题 |
| |
| 引用本文： | 赵保华,钱兰,郭雄辉.被动测试中网络监测问题[J].天津大学学报(自然科学与工程技术版),2006,39(7):801-805. |
| |
| 作者姓名： | 赵保华 钱兰 郭雄辉 |
| |
| 作者单位： | 中国科学技术大学计算机系,合肥230027 |
| |
| 基金项目： | 国家自然科学基金;中国科学院资助项目;国家研究发展基金 |
| |
| 摘 要： | 研究了被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况．先把该问题归结为图的顶点覆盖问题，它是一个NP完全问题；接着讨论了在网络拓扑是树的特殊情形下带权和不带权顶点覆盖问题的解，并给出了树结构上带权顶点覆盖问题的线性时间算法；然后在已有的一个近似比为2的算法基础上。结合树结构上不带权顶点覆盖问题的算法给出了图的不带权顶点覆盖问题的一个改进算法，最后用实验验证了改进算法能使观察者数目减小20％左右．
|
| 关 键 词： | 被动测试 NP完全问题 近似算法 |
| 文章编号： | 0493-2137（2006）07-0801-05 |
| 收稿时间： | 2005-03-25 |
| 修稿时间： | 2005-03-252006-02-28 |
Network Monitor Problem in Passive Testing |
| |
| ZHAO Bao-hua,QIAN Lan,GUO Xiong-hui.Network Monitor Problem in Passive Testing[J].Journal of Tianjin University(Science and Technology),2006,39(7):801-805. |
| |
| Authors: | ZHAO Bao-hua QIAN Lan GUO Xiong-hui |
| |
| Affiliation: | Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China |
| |
| Abstract: | 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%. |
| |
| Keywords: | passive testing NP-complete problem approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
