Analysis of Efficient Monitoring Method for the Network Flow
网络流量的有效测量方法分析

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