Approximation Algorithm for Weighted Weak Vertex Cover  

作　　者：YongZhang HongZhu 

机构地区：[1]DepartmentofComputerScienceandEngineering,FudanUniversity,Shanghai200433,P.R.China [2]LaboratoryforIntelligentInformationProcessing,FudanUniversity,Shanghai200433,P.R.China

出　　处：《Journal of Computer Science & Technology》2004年第6期782-786,共5页计算机科学技术学报（英文版）

基　　金：科技部资助项目，国家自然科学基金，上海市科技发展基金

摘　　要：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 graphG=(V,E). In this paper, we give an approximation algorithm to solve it, which has the approximation ratio lnd+1, whered is the maximum degree of the vertex in graphG, and improve the previous work. Keywords weak vertex cover - NP-hard - approximation algorithm NoteThis work is supported by the Ministry of Science and Technology of China (Grant No.2001CCA03000), the National Natural Science Foundation of China (Grant No.60273045), and the Shanghai Science and Technology Development Foundation (Grant No.025115032).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 graphG=(V,E). In this paper, we give an approximation algorithm to solve it, which has the approximation ratio lnd+1, whered is the maximum degree of the vertex in graphG, and improve the previous work. Keywords weak vertex cover - NP-hard - approximation algorithm NoteThis work is supported by the Ministry of Science and Technology of China (Grant No.2001CCA03000), the National Natural Science Foundation of China (Grant No.60273045), and the Shanghai Science and Technology Development Foundation (Grant No.025115032).

关 键 词：weak vertex cover NP-HARD approximation algorithm 

分 类 号：TN915.01[电子电信—通信与信息系统]