algorithm
最小頂点カバーの多項式時間限定アルゴリズム

前書き

パラメーター

備考

アルゴリズム擬似コード

アルゴリズムPMinVertexCover（グラフG）

入力グラフG

出力最小頂点カバーセット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はグラフGの最小頂点カバー

度の最大値が（n-1）であり、nが頂点の数である場合、ソートの時間複雑度はO（n）になるので、度合いに応じて頂点をソートするためにバケットソートを使用することができる。