An Advanced Approach for Minimum Vertex Cover Problem ECE Seminar Topic

Introduction to An Advanced Approach for Minimum Vertex Cover Problem:

Introduction:

This paper proposes certain techniques for reducing the minimum vertex problem so the selected vertices cover all the edges in the graph. There  are various algorithms to reduce the minimum vertex problem all of them follow heuristic based approach  we are not able to get optimal solution in the same manner. We can get near results for the optimal solution by using greedy algorithm. In this paper we will discuss minimum advance vertex cover algorithm to find the optimal solution for the minimum vertex problem.

Brief into algorithm:

The advance algorithm is to find small subset of vertices so that every subset has at least one endpoint. There will be at least three approaches for obtaining NP completeness. Suppose if the given inputs are small then the algorithm with exponential running will be the best approach. The second approach is to eliminate the important special cases that are solvable in polynomial time. Approximation algorithms are efficient in producing near optimal solution for the minimum vertex problem. In most cases researchers follow greedy  algorithm but it does not produces minimal optimal solution but is seems good at that point of time. By using advance vertex cover algorithm we calculate the time complexity  O(n²). this is obtained by making a list of the vertices and transverse vertices. By using transverse and searching connected vertex from transverse vertex we will calculate the time complexity.

Conclusions:

By using heuristic and greedy we may not get the near solution but by using advance vertex cover algorithm we can get near optimal solution by introducing simple O(n²) time complexity.  But by using O(n²) time complexity we can obtain the optimal solution for the minimum vertex problem.

Download An Advanced Approach for Minimum Vertex Cover Problem ECE Seminar Topic.

Related Projects

Leave a Reply

Your email address will not be published. Required fields are marked *