论文部分内容阅读
网络流量监测点问题可以抽象为图的最小弱顶点覆盖问题,而求解最小弱顶点覆盖问题是一个NP难题。该文利用图论中关联矩阵的概念,提出了一个近似算法,并分析了算法的复杂性。在此基础上将该算法拓展到顶点加权情况下图的弱顶点覆盖问题。理论分析和仿真实验表明,比较现有的算法,新的算法能够发现更小的弱顶点覆盖集,且具有更好的可扩展性。