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

kousuke.hatenablog.com 大事なことに気が付いたので、前回の修正。単純な無向グラフに対し、をサイズkのクリークが含まれるかどうかを判定する関数とする。グラフGに自身を除く全頂点に接続する頂点がある場合、それらは必ず最大クリークに含まれる。そのよ…

kousuke.hatenablog.comn頂点の完全グラフを、独立グラフ(頂点のみで辺がないグラフ)をとする。n頂点のグラフがある。 このときからへひとつづつ辺を消していく順序集合のうち、を含む順序の集合を定めることができる。このときのどの順序を通ってもの補グラ…

kousuke.hatenablog.com 頂点に関しては極大グラフが１つになるまでは(底を小さくするという意味ではもう少し改善はあるのだろうけど)、たぶん最速だとおもう。あとは補グラフの辺数wをなるべく少なく消しながら、進めばよい。 これは一緒に補グラフの最大独…

修正しました。 kousuke.hatenablog.com (以下、古い内容)をサイズkのクリークが含まれるかどうかを判定する関数とする。(0: 含まない or 1 : 含む)最大サイズkのクリークを含む、単純な無向グラフがあるとする。頂点vに隣接している頂点の集合をとし、に対…

すこしコードを変更している。興味ある人はpaiza.ioで動かしてみてほしい。 https://paiza.io/projects/14TYw6RR2KIPBLRjSNCPrgV=1000、E=9988、20彩色可能、最大次数 69、次数の分布具合は下記のグラフを参考。 最大クリークは8。列挙しているわけではない…