%0 Journal Article
%T Model and Algorithm Research for Seeking Efficient Monitor-Nodes Measuring Network Traffic<br>网络流量有效监测点的设置模型及求解算法研究
%A Jiang Hong-yan
%A Lin Ya-ping
%A Huang Sheng-ye
%A <br>蒋红艳
%A 林亚平
%A 黄生叶
%J 电子与信息学报
%D 2006
%I 
%X 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.
%K Graph
%K Weak vertex cover
%K Nodes with weights
%K Flow conservation
%K NP-hard
%K Incidence matrix<br>图论
%K 弱顶点覆盖
%K 顶点加权
%K 流守恒
%K NP难题
%K 关联矩阵
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=1319827C0C74AAE8D654BEA21B7F54D3&jid=EFC0377B03BD8D0EF4BBB548AC5F739A&aid=299841B0B8C2229F&yid=37904DC365DD7266&vid=D3E34374A0D77D7F&iid=E158A972A605785F&sid=04CF423CEE45E258&eid=895BB10EB8F3BD49&journal_id=1009-5896&journal_name=电子与信息学报&referenced_num=1&reference_num=6