网络流量有效监测点的设置模型及求解算法研究
Model and Algorithm Research for Seeking Efficient Monitor-Nodes Measuring Network Traffic作者机构:湖南大学计算机与通信学院长沙410082
出 版 物:《电子与信息学报》 (Journal of Electronics & Information Technology)
年 卷 期:2006年第28卷第4期
页 面:753-756页
核心收录:
学科分类:12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 0809[工学-电子科学与技术(可授工学、理学学位)] 07[理学] 08[工学] 070104[理学-应用数学] 081201[工学-计算机系统结构] 0701[理学-数学] 0812[工学-计算机科学与技术(可授工学、理学学位)]
主 题:图论 弱顶点覆盖 顶点加权 流守恒 NP难题 关联矩阵
摘 要:网络流量监测点问题可以抽象为图的最小弱顶点覆盖问题,而求解最小弱顶点覆盖问题是一个NP难题。该文利用图论中关联矩阵的概念,提出了一个近似算法,并分析了算法的复杂性。在此基础上将该算法拓展到顶点加权情况下图的弱顶点覆盖问题。理论分析和仿真实验表明,比较现有的算法,新的算法能够发现更小的弱顶点覆盖集,且具有更好的可扩展性。