はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける最大クリーク問題、最大独立集合問題まとめ

はじめに

  • 最大クリーク問題
    • 無向グラフの中での最大の完全グラフを求める問題
    • 最大クリークを半分前列挙で効率よく扱うテクがある
  • 最大独立集合問題
    • 無向グラフの中で、どの頂点間にも辺が無い最大成分を求める問題
    • 最大クリーク問題の逆の問題