earticle

영어

Approximation methods are best way to deal NP optimization problems and MVC is one of these. In this research paper we have presented a new extra fast approximation algorithm for solving MVC generally in all graphs. The proposed algorithm is named degree contribution algorithm (DCA), a new data structure proposed and employed in this algorithm, name degree contribution. It is first time in literature that such a sophisticated data structure for graphs is proposed which take account of whole graph for each node contribution value. All decisions regarding vertices are made on the basis of the proposed data structure. Effectiveness of DCA is shown by applying it to best available benchmarks and after large number of experiments worst approximation ratio recorded was 1.041 and an average approximation ratio was 1.005. These results show that algorithm can perform well in solving graphs faster as compared to other algorithms present.