首页> 中文期刊> 《软件学报》 >基于原始对偶方法求解网络流量监测集算法

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

         

摘要

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

著录项

  • 来源
    《软件学报》 |2006年第4期|838-844|共7页
  • 作者单位

    国防科学技术大学;

    计算机学院;

    湖南;

    长沙;

    410073;

    国防科学技术大学;

    电子科学与工程学院;

    湖南;

    长沙;

    410073;

    国防科学技术大学;

    计算机学院;

    湖南;

    长沙;

    410073;

    国防科学技术大学;

    计算机学院;

    湖南;

    长沙;

    410073;

    国防科学技术大学;

    计算机学院;

    湖南;

    长沙;

    410073;

    浙江师范大学;

    计算机学院;

    浙江;

    金华;

    321004;

  • 原文格式 PDF
  • 正文语种 chi
  • 中图分类 理论、方法;
  • 关键词

    弱顶点覆盖; NP难的; 近似算法; 流守恒;

相似文献

  • 中文文献
  • 外文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号