algorithm polynomial-time bounded algorithm for Minimum Vertex Cover

Help us to keep this website almost Ad Free! It takes only 10 seconds of your time:
> Step 1: Go view our video on YouTube: EF Core Bulk Insert
> Step 2: And Like the video. BONUS: You can also share it!

Introduction

This is a polynomial algorithm for getting the minimum vertex cover of connected undirected graph. The time complexity of this algorithm is O(n2)

Parameters

VariableMeaning
GInput connected un-directed graph
XSet of vertices
CFinal set of vertices

Remarks

The first thing you have to do in this algorithm to get all of the vertices of the graph sorted in descending order according to its degree.

After that you have iterate on them and add each one to final vertices set which don't have any adjacent vertex in this set.

In the final stage iterate on the final vertices set and remove all of the vertices which have one of its adjacent vertices in this set.



Got any algorithm Question?