わきゃらん

平面グラフにおいて、subgraph isomorphism problem(平面グラフGと固定したグラフHにおいて,
GはHと同型な部分グラフを(いくつ)含むか?)は線形時間で解ける。
これは、Hのサイズをパラメータとして、FPTになるという寸法だ。
アルゴリズムの中で、tree decomposition上のDPでそのようなisomorphismが存在するかを
計算していくのだが,よくわからん
[cs/9911003] Subgraph Isomorphism in Planar Graphs and Related Problems
[0909.4692] Planar Subgraph Isomorphism Revisited