被动测试中观察者放置问题

• 作者: 屈玉贵 赵保华 郭雄辉 钱兰
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 被动测试 NP完全问题 通信有限状态机
• 年，卷（期）: 2005,（10）
• 所属期刊栏目: 算法理论
• 页码范围: 1815-1819
• 页数: 5页
• 分类号: TP301.6
• 字数: 4197字
• 语种: 中文

摘要

在被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况是一个很有实际应用价值的问题.先证明了该问题是一个NP完全问题;接着讨论了在网络拓扑是树的特殊情形下该问题的解,并给出了针对树结构的一个线性时间算法;然后在一个已有的近似比为2的算法基础上给出了一个改进算法并证明了其近似比为2-O(1),最后用实验来验证了改进算法的有效性,指明了进一步的研究方向.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	屈玉贵	中国科学技术大学计算机科学与技术系	98	1088	19.0	27.0
2	赵保华	中国科学技术大学计算机科学与技术系	152	1481	21.0	28.0
3	郭雄辉	中国科学技术大学计算机科学与技术系	8	54	4.0	7.0
4	钱兰	中国科学技术大学计算机科学与技术系	6	18	3.0	3.0