欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
研究了被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况．先把该问题归结为图的顶点覆盖问题，它是一个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%.
同期刊论文项目
同项目期刊论文
期刊信息
位置：