Algorithm Pseudo Code
suggest changeAlgorithm 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)
Found a mistake? Have a question or improvement idea?
Let me know.
Table Of Contents