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

作者：刘湘辉; 殷建平; 卢锡城; 蔡志平; 赵建民

来源：软件学报, 2006, (04): 838-844.

• 弱顶点覆盖
• NP难的
• 近似算法
• 流守恒 weak vertex cover
• NP-hard
• approximation algorithm
• flow conservation

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

• 单位
  中国人民解放军国防科学技术大学; 浙江师范大学