AN APPROXIMATION ALGORITHM FOR WEAK VERTEX COVER PROBLEM IN IP NETWORK TRAFFIC MEASUREMENT
In order to plan the network construction reasonable and ensure the quality of network service, it is important to measure the Linkbandwidth utilization and get the flow information. One of the methods to monitor network efficiently is based on flow-conservation, and the problem of searching a solution for this method could be deduced to solving weak vertex cover problem, which has been proved NP-hard. So finding an optimum solution for weak vertex cover problem is critical for the network measurement based on flow-conservation. In this paper, we proposed a method using topology matrix to represent the topology graph information and remove the redundant nodes through back tracing the result node set. This method can get a better solution than general greedy algorithm. An example and emulation have been provided to exemplify this method.
network measurement weak vertez cover flow-conservation greedy algorithm
Yongguo Zeng Dezheng Wang Wei Liu Ao Xiong
State Key laboratory of Networking and Switching Technology,Beijing University of Posts and Telecomm Department of Network Management Product, Zhongxing Telecom Equipment Company, Nanjing
国际会议
北京
英文
182-186
2009-11-06（万方平台首次上网日期，不代表论文的发表时间）