Performance Evaluation of Vertex Cover and Set Cover Problem using Optimal Algorithm
B. M. Monjurul Alom, Mohammad Abdur Rouf · 2011
An appr oximation algorithm for a procedure that always provides some kind of solution, although it may fail to find the optimal solution. The approximate algorithms generally faster which can be proved to be close to the optimal solutions. The existing approximate algorithm for vertex cover and set cover problem is not optimal. To overcome this limitation, in this paper we have presented two new algorithms for vertex cover and set cover problem that provides the optimal solution that is better than approximate solution. The presented optimal algorithm and the existing well known approximation algorithm have almost the same time complexity but with respect to the solution our optimal algorithm outperforms compared to the existing approximation algorithm.