ei1333の日記

ぺこい

木幅が2以下のグラフの木分解と動的計画法

なんだこのよくわからんたいとる

卒論を書いているだけだと精神衛生上よくないので, つらくなったときに書いていました.

木幅・木分解についてと, 木分解上で動的計画法をするアルゴリズムについて解説します.

例えば最大独立集合は木幅  {t} として  {O(2^{t+1} t^2 V)} とかで解けます.

また, 一般に木分解を求めるのはヒューリスティックなどをする必要があり最悪ケースを考慮する競プロ的には難しい(難しくなかったら教えてください)ので一般グラフに対する木分解はどこかの記事や本などを読んで頂くこととして, ここでは有用そうな木幅が  {2} 以下のグラフの木分解について解説します. ちなみに木幅が  {2} 以下のグラフは カクタス, なもりグラフ, 外平面グラフなどの, Series-parallel graph(直並列グラフ) などを含みます. カクタスみたいなのはこどふぉでよくみるかも.

続きを読む