研究日記

最近恐ろしく研究が進まないので、自分用のメモをつけることにする。
今はplanar graphのvertex coverやindependent setとかのfixed parameter algorithmを勉強中。
Parameterized complexity: exponential speed-up for planar graph problems
著者らによるseparator theoremを使った方法でO(c^sqrt(k) + Tk(n, k))(Tk(n,k)はkernelを求める時間)のアルゴリズムがあるが、cが大きいという問題があったが、Layer decompositionなるものをつかって定数を小さくしたらしい。
まだ理解できていないが、おもしろそう