Header menu link for other important links
An Articulation Point-Based Approximation Algorithm for Minimum Vertex Cover Problem
Thenepalle J.K,
Published in Springer International Publishing
Pages: 281 - 289

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.

About the journal
JournalData powered by TypesetTrends in Mathematics Advances in Algebra and Analysis
PublisherData powered by TypesetSpringer International Publishing
Open Access0