Approximation Algorithm for Weighted Weak Vertex Cover

The problem of efficiently monitoring the network flow is regarded as the problem to find out the minimum weighted weak vertex cover set for a given graph G=(V, E). In this paper, we give an approximation algorithm to solve it, which has the approximation ratio ln d + 1, where d is the maximum degree of the vertex in graph G, and improve the previous work.