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

摘要：

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

关键词： 弱顶点覆盖 NP难 网络流量检测 近似算法 邻接矩阵

作者: 石恒华 何泾沙 许鑫

作者单位: 北京工业大学计算机学院 北京 100124 北京工业大学软件学院 北京 100124

会议类型: 国内会议

会议名称: 第八届全国信息隐藏与多媒体安全学术大会暨湖南省计算机学会第十一届学术年会(CIHW 2009)

会议地点: 长沙

会议语种:中文

页码: 370-374

在线出版日期: 2009-03-01（万方平台首次上网日期，不代表论文的发表时间）