Algorithms Minimum Vertex Cover suggest change

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)

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents