基于原始对偶方法求解网络流量监测集算法

• 作者: 刘湘辉 卢锡城 殷建平 蔡志平 赵建民
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 弱顶点覆盖 NP难的 近似算法 流守恒
• 年，卷（期）: 2006,（4）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 838-844
• 页数: 7页
• 分类号: TP301
• 字数: 8345字
• 语种: 中文

摘要

考虑网络节点的流守恒特性,网络流量的有效监测问题可抽象为求给定图G(V,E)的最小弱顶点覆盖集的问题和基于流划分的最小弱顶点覆盖集的问题,这是NP难的问题.首先分析了弱顶点覆盖集的约束关系,并给出了问题的整数规划形式.然后利用原始对偶方法构造了求解最小弱顶点覆盖集的近似算法,并分析了算法的比界为2.进一步分析了求解基于最大流划分的最小弱顶点覆盖集的近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵建民	浙江师范大学计算机学院	121	1027	18.0	25.0
2	卢锡城	国防科学技术大学计算机学院	70	1620	21.0	38.0
3	蔡志平	国防科学技术大学计算机学院	38	561	13.0	23.0
4	殷建平	国防科学技术大学计算机学院	68	1057	17.0	30.0
5	刘湘辉	国防科学技术大学计算机学院	7	147	6.0	7.0