The minimum vertex cover problem (MVCP) is a well-known NP complete combinatorial optimization problem. The aim of this paper is to present an approximation algorithm for minimum vertex cover problem (MVCP). The algorithm construction is based on articulation points/cut vertices and leaf vertices/pendant vertices. The proposed algorithm assures the near optimal or optimal solution for a given graph and can be solved in polynomial time. A numerical example is illustrated to describe the proposed algorithm. Comparative results show that the proposed algorithm is very competitive compared with other existing algorithms.
View more info for "An Articulation Point-Based Approximation Algorithm for Minimum Vertex Cover Problem"
|Data powered by TypesetTrends in Mathematics Advances in Algebra and Analysis
|Data powered by TypesetSpringer International Publishing