2017-04-30から1日間の記事一覧

最大クリークの途中で補グラフが出てくる話

kousuke.hatenablog.com 前回、ワーストケースでになると書いた。FPTでの幅はほぼ極大グラフの数でよいとおもっているけど、それをなぜ補グラフでやろうとしているか? 簡単に言うと補グラフに辺があれば、極大集合が2つ以上あるから。最大クリーク判定の式を…