网络流量的有效测量方法分析

刘湘辉; 殷建平; 唐乐乐; 赵建民

引用本文:	刘湘辉,殷建平,唐乐乐,赵建民.网络流量的有效测量方法分析.软件学报,2003,14(2):300-304

【打印本页】【下载PDF全文】【查看/发表评论】【EndNote】【RefMan】【BibTex】

←前一篇|后一篇→

过刊浏览高级检索

本文已被：浏览 5706次下载 6577次	码上扫一扫！
分享到：微信更多字体:加大+\|默认\|缩小-
网络流量的有效测量方法分析
刘湘辉¹, 殷建平¹, 唐乐乐¹, 赵建民²
1.国防科学技术大学,计算机学院,湖南,长沙,410073;2.浙江师范大学,计算机学院,浙江,金华,321004

摘要:

把网络流量的有效测量问题抽象为求给定图G=(V,E)的最小弱顶点覆盖集的问题.给出了一个求最小弱顶点覆盖集的近似算法,并证明了该算法具有比界2(lnd+1),其中d是图G中顶点的最大度.指出了该算法的时间复杂性为O(|V|²).

关键词: 弱顶点覆盖 NP难的近似算法流守恒

DOI：

分类号:

基金项目:Supported by the National Natural Science Foundation of China under Grant No.69933030 (国家自然科学基金)

Analysis of Efficient Monitoring Method for the Network Flow

LIU Xiang-Hui,YIN Jian-Ping,TANG Le-Le,ZHAO Jian-Min

Abstract:

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|²).

Key words: weak vertex cover NP-hard approximation algorithm flow conservation