2

私にグラフのクリークを与えるブラックボックス（/アルゴリズム）があるとしましょう。そこからクリークカバーを見つける方法はありますか？

私が見つけようとしている直感的なアイデアが写真に示されています。ブラックボックスの部分を探しています。さらに説明が必要な場合は、お気軽にお問い合わせください。クリークのエッジを削除してグラフを更新するアイデアがあります。うまくいくかはわかりません。他にもアイデアお待ちしております。

また、近似クリーク被覆アルゴリズムの良いリファレンスを教えていただけると大変助かります。 ここに画像の説明を入力

4

1 に答える 1

1

http://mathworld.wolfram.com/CliqueCoveringNumber.html

新しいグラフには、カバーを解決するために使用されるクリークが欠落している可能性があるため、エッジを削除しても役に立ちません。

    B
  / | \
A   |  D
  \ | /
    C

ABC から始めて、そのエッジ AB AC と BC を削除すると、アルゴリズムは BCD クリークを見つけることができなくなります。

クリーク カバー数を計算する前に、グラフのすべての最大クリークが必要になります。

AllCliques = GetAllCliques()
MaximalCliques = AllCliques
For Each ckA in MaximalCliques
  For Each ckB in MaximalCliques.Excluding(ckA)
    If all vertices in ckA are in ckB Then MaximalCliques.Remove(ckA)
    If all vertices in ckB are in ckA Then MaximalCliques.Remove(ckB)
Return MaximalCliques

次に、すべての最大クリークからクリークカバー数を見つけるための単純なアプローチが順列を介して実行され、チェックされます

MinCover = MaximalCliques.Count
For Each ckList in Permute(MaximalCliques)
  Cover = 0
  TestSet = Graph.Vertices
  For Each ck in ckList
    TestSet.Remove(ck.Vertices)
    Cover = Cover + 1
    If TestSet.Count = 0 Then Break
  If Cover < MinCover Then MinCover = Cover
Return MinCover
于 2015-08-04T12:48:34.730 に答える