Approximation algorithm for weighted weak vertex cover

被引：9

作者：

Zhang, Y ^{[1
]}

Zhu, H

机构：

[1] Fudan Univ, Dept Comp Sci & Engn, Shanghai 200433, Peoples R China

[2] Fudan Univ, Lab Intelligent Informat Proc, Shanghai 200433, Peoples R China

来源：

JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY | 2004年 / 19卷 / 06期

基金：

中国国家自然科学基金;

关键词：

weak vertex cover; NP-hard; approximation algorithm;

D O I：

10.1007/BF02973439

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 In d+ 1, where d is the maximum degree of the vertex in graph G, and improve the previous work.

引用

页码：782 / 786

页数：5