Getting started with algorithm Sorting Bubble Sort Algorithm Complexity Graph Dynamic Programming Kruskal's Algorithm Greedy Algorithms Searching Big-O Notation Bellman–Ford Algorithm Merge Sort Binary Search Trees Trees Insertion Sort Hash Functions Travelling Salesman Substring Search Dijkstra’s Algorithm Floyd-Warshall Algorithm Breadth-First Search Bucket Sort Quicksort Depth First Search Knapsack Problem Counting Sort Cycle Sort Heap Sort Prim's Algorithm Matrix Exponentiation Pigeonhole Sort Radix Sort Equation Solving Odd-Even Sort Pseudocode Catalan Number Algorithm Integer Partition Algorithm A* Pathfinding Shell Sort Selection Sort Pancake Sort Longest Common Subsequence Longest Increasing Subsequence Maximum Path Sum Algorithm Maximum Subarray Algorithm Dynamic Time Warping Pascal's Triangle Line Algorithm Shortest Common Supersequence Problem Sliding Window Algorithm Applications of Greedy technique Online algorithms Fast Fourier Transform A* Pathfinding Algorithm Check if a tree is BST or not Binary Tree traversals Lowest common ancestor of a Binary Tree Graph Traversals polynomial-time bounded algorithm for Minimum Vertex Cover Multithreaded Algorithms Algo:- Print a m*n matrix in square wise Check two strings are anagrams Edit Distance Dynamic Algorithm Applications of Dynamic Programming Knuth Morris Pratt (KMP) Algorithm

polynomial-time bounded algorithm for Minimum Vertex Cover

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.

Algorithm Pseudo Code

Algorithm PMinVertexCover (graph G)

Input connected graph G

Output Minimum Vertex Cover Set C

Set C <- new Set<Vertex>() 

Set X <- new Set<Vertex>() 

X <- G.getAllVerticiesArrangedDescendinglyByDegree()

for v in X do
    List<Vertex> adjacentVertices1 <- G.getAdjacent(v)

    if !C contains any of adjacentVertices1 then
        
        C.add(v)

for vertex in C do

    List<vertex> adjacentVertices2 <- G.adjacentVertecies(vertex)

    if C contains any of adjacentVertices2 then
        
        C.remove(vertex)

        
return C

C is the minimum vertex cover of graph G

we can use bucket sort for sorting the vertices according to its degree because the maximum value of degrees is (n-1) where n is the number of vertices then the time complexity of the sorting will be O(n)

Parameters:

Variable	Meaning
G	Input connected un-directed graph
X	Set of vertices
C	Final set of vertices

Contributors

Topic Id: 9535

Example Ids: 29463

This site is not affiliated with any of the contributors.