We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Yong Zhang, Hong Zhu. Approximation Algorithm for Weighted Weak Vertex Cover[J]. Journal of Computer Science and Technology, 2004, 19(6).
Citation: Yong Zhang, Hong Zhu. Approximation Algorithm for Weighted Weak Vertex Cover[J]. Journal of Computer Science and Technology, 2004, 19(6).

Approximation Algorithm for Weighted Weak Vertex Cover

More Information
  • Published Date: November 14, 2004
  • 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.
  • Related Articles

    [1]Jian-Xin Wang, Xiao-Shuang Xu, Jian-Er Chen. Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs[J]. Journal of Computer Science and Technology, 2008, 23(5): 763-768.
    [2]Florian Diedrich, Rolf Harren, Klaus Jansen, Ralf Th&oumlle, Henning Thomas. Approximation Algorithms for 3D Orthogonal Knapsack[J]. Journal of Computer Science and Technology, 2008, 23(5): 749-762.
    [3]Ya-Feng Wu, Yin-Long Xu, Guo-Liang Chen. Approximation Algorithms for Steiner Connected Dominating Set[J]. Journal of Computer Science and Technology, 2005, 20(5): 713-716.
    [4]Zi-Mao Li, Da-Ming Zhu, Shao-Han Ma. Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [5]HE Yong, CHEN Ting. A New Approximation Algorithm for Sorting of Signed Permutations[J]. Journal of Computer Science and Technology, 2003, 18(1).
    [6]GU Xiaodong, CHEN Guoliang, XU Yinlong. Deep Performance Analysis of Refined Harmonic Bin Packing Algorithm[J]. Journal of Computer Science and Technology, 2002, 17(2).
    [7]LIU Tian. A Note on Closeness between NP-Hard Sets and C=P[J]. Journal of Computer Science and Technology, 2000, 15(2): 194-195.
    [8]ZHANG Li'ang, ZHANG Yin. Approximation for- Knapsack Problemswith Multiple Constraints[J]. Journal of Computer Science and Technology, 1999, 14(4): 289-297.
    [9]Chen Bin, Hong Yong. FCV_1: A New Fast Greedy Covering Algorithm[J]. Journal of Computer Science and Technology, 1998, 13(4): 369-374.
    [10]Cheng Qi, Zhu Hong. MNP: A Class of NP Optimization Problems[J]. Journal of Computer Science and Technology, 1997, 12(4): 306-313.

Catalog

    Article views (20) PDF downloads (1527) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return