| 网络流量的有效测量方法分析 |
| |
| 引用本文： | 刘湘辉,殷建平,唐乐乐,赵建民.网络流量的有效测量方法分析[J].软件学报,2003,14(2):300-304. |
| |
| 作者姓名： | 刘湘辉 殷建平 唐乐乐 赵建民 |
| |
| 作者单位： | 1. 国防科学技术大学,计算机学院,湖南,长沙,410073
2. 浙江师范大学,计算机学院,浙江,金华,321004 |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant No.69933030 (国家自然科学基金) |
| |
| 摘 要： | 把网络流量的有效测量问题抽象为求给定图G=(V,E)的最小弱顶点覆盖集的问题.给出了一个求最小弱顶点覆盖集的近似算法,并证明了该算法具有比界2(lnd+1),其中d是图G中顶点的最大度.指出了该算法的时间复杂性为O(|V|2).
|
| 关 键 词： | 弱顶点覆盖 NP难的 近似算法 流守恒 |
| 文章编号： | 1000-9825/2003/14(02)0300 |
| 收稿时间： | 2002/5/10 0:00:00 |
| 修稿时间： | 2002年5月10日 |
Analysis of Efficient Monitoring Method for the Network Flow |
| |
| LIU Xiang-Hui,YIN Jian-Ping,TANG Le-Le and ZHAO Jian-Min.Analysis of Efficient Monitoring Method for the Network Flow[J].Journal of Software,2003,14(2):300-304. |
| |
| Authors: | LIU Xiang-Hui YIN Jian-Ping TANG Le-Le and 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|2). |
| |
| Keywords: | weak vertex cover NP-hard approximation algorithm flow conservation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
