earticle

영어

Minimum vertex cover is very important among the NP-optimization problems and got the attention of the researchers in the past decade. Approximation techniques are used to solve the NP problems to get either optimal or near optimal solutions in polynomial time. In this paper, a modified vertex support algorithm is proposed that make use of same data structure as that of VSA but with different vertex selection criteria. Proposed algorithm is called advance vertex support algorithm (AVSA), it takes into account all the neighbors of a vertex twice while selection as surrounding vertices are very important for the decision. AVSA is analyzed experimentally against all benchmarks and compared with some better algorithms already present. The experimental results show that the worst approximation ratio was 1.032 with a ratio of average approximation 1.006. A comparative analysis with other algorithms indicates that AVSA can provide the best solution among them the minimum time requirements. Simplicity in design can give advantages to implement in various fields of application with minimum overhead.