algorithm
最小頂点カバーの多項式時間限定アルゴリズム
サーチ…
前書き
これは、接続された無向グラフの最小頂点カバーを得るための多項式アルゴリズムです。このアルゴリズムの時間複雑度はO(n2)であり、
パラメーター
変数 | 意味 |
---|---|
G | 入力された無向グラフ |
バツ | 頂点の集合 |
C | 最終的な頂点のセット |
備考
グラフの頂点のすべてを次数で降順でソートするには、まずこのアルゴリズムで行う必要があります。
その後、それらを反復して、このセットに隣接する頂点を持たない最終頂点セットにそれぞれを追加します。
最後の段階で、最終的な頂点セットを反復し、このセット内の隣接する頂点の1つを有する頂点のすべてを除去する。
アルゴリズム擬似コード
アルゴリズム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)になるので、度合いに応じて頂点をソートするためにバケットソートを使用することができる。
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow