摘要
网络流量监测点问题可以抽象为图的最小弱顶点覆盖问题,而求解最小弱顶点覆盖问题是一个NP难题。该文利用图论中关联矩阵的概念,提出了一个近似算法,并分析了算法的复杂性。在此基础上将该算法拓展到顶点加权情况下图的弱顶点覆盖问题。理论分析和仿真实验表明,比较现有的算法,新的算法能够发现更小的弱顶点覆盖集,且具有更好的可扩展性。
The problem of seeking monitor-nodes for measuring the network traffic is regarded as the problem of finding out the minimum weak vertex cover of a graph which is NP-hard. An approximation algorithm is proposed in this paper based on the concept of incidence matrix in Graph. Also the complexity of the algorithm is analyzed. Furthermore, the algorithm is expanded to seek the minimum weak vertex cover for a graph that has weights on the nodes. The theoretical analysis and the simulation results show that the novel algorithm is more scalable than the traditional algorithms, and can find smaller weak vertex cover.
出处
《电子与信息学报》
EI
CSCD
北大核心
2006年第4期753-756,共4页
Journal of Electronics & Information Technology
基金
湖南省自然科学基金(03JJY3098)资助课题
关键词
图论
弱顶点覆盖
顶点加权
流守恒
NP难题
关联矩阵
Graph, Weak vertex cover, Nodes with weights, Flow conservation, NP-hard, Incidence matrix