基于邻接矩阵的网络流量检测点设置算法

摘要

在研究网络流量的有效测量问题时，考虑网络节点的流守恒，把网络流量监测点问题抽象为无向图的最小弱顶点覆盖问题，这是一个NP难的问题.基于图论中邻接矩阵的概念，提出一个近似算法，通过重复删除邻接矩阵中所有行元素之和不超过1的节点对应的行和列，得到最小弱顶点覆盖集.在此基础上通过预先递归去除无向图中1度节点，满足任意节点度数都大于或等于2的最小弱顶点覆盖问题求解条件，并将递归节点作为该近似算法的入口点.仿真实验表明，与现有算法相比，新算法具有更好的性能，能够发现更小的弱顶点覆盖集.