NMVSA Greedy Solution for Vertex Cover Problem

Minimum vertex cover (MVC) is a well-known NP-Complete optimization problem. The importance of MVC in theory and practical comes from the wide range of its applications. This paper describes a polynomial time greedy algorithm to find near optimal solutions for MVC. The new algorithm NMVAS is a modification of already existed algorithm called MVAS which uses the same principle of selecting candidate from the neighborhood of the vertex with a modification in the selection procedure. A comparative study is conducted between the NMVAS and MVAS which shows that the proposed algorithm NMVSA provides better or equal results in the most cases of the underlying data sets which leads to a better average approximation ratio of NMVAS. NMVAS inherits the simplicity of the original algorithm.

@article{Eshtay2016,
  title     = {NMVSA Greedy Solution for Vertex Cover Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {7},
  number    = {3},
  year      = {2016},
  publisher = {The Science and Information Organization},
  author    = {Mohammed Eshtay and Azzam Sleit and Ahmad Sharieh},
  doi       = {10.14569/IJACSA.2016.070309},
  url       = {https://doi.org/10.14569/IJACSA.2016.070309}
}