%0 Journal Article
%T Analysis of Efficient Monitoring Method for the Network Flow<br>网络流量的有效测量方法分析
%A LIU Xiang-Hui
%A YIN Jian-Ping
%A TANG Le-Le
%A ZHAO Jian-Min
%A <br>刘湘辉
%A 殷建平
%A 唐乐乐
%A 赵建民
%J 软件学报
%D 2003
%I 
%X In this paper, the problem of efficient monitoring for the network flow is regarded as the problem to find out the minimum weak vertex cover set for a given graph G=(V,E). An approximation algorithm is presented. It is proved that the algorithm has a ratio bound of 2(lnd+1), where d is the maximum degree of the vertices in graph G. It is showed that the running time of the algorithm is O(|V|2).
%K weak vertex cover
%K NP-hard
%K approximation algorithm
%K flow conservation<br>弱顶点覆盖
%K NP难的
%K 近似算法
%K 流守恒
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=B18E4A17BD0FAA47&yid=D43C4A19B2EE3C0A&vid=F3583C8E78166B9E&iid=0B39A22176CE99FB&sid=B1E36BF7B9783A85&eid=8ED630AD8C61FAE8&journal_id=1000-9825&journal_name=软件学报&referenced_num=23&reference_num=5