木分解
1970年代の始めに、グラフの上の広い範囲の組合せ最適化問題が、グラフの次元(木幅に関係するパラメータ)が制限されている場合には動的計画法によって効率的に解けることが知られていた。その後、多くのNP完全なアルゴリズム的問題が固定された木幅のグラフに対して木分解を用いた動的計画法で効率的に解けることを、1980年代の終わりに数人の研究者が独立に発見した。
例として、木幅kのグラフの最大独立集合を見つける問題を考える。この問題を解くために、木分解のノードを任意に一つ選んで根とする。木分解のノードXiに対して、DiをXiの下のノードXj全体の和集合とする。独立集合S ⊂ Xiに対して、A(S,i)をDiの独立集合Iであって、 I ∩ Xi = Sを満たす最大のもののサイズとする。同様に、隣接するノードXi , Xj(Xjの方が根に近い)と独立集合S ⊂ Xi ∩ Xjに対して、B(S,i,j)をDiの独立集合Iであって、 I ∩ Xi ∩ Xj = Sを満たす最大のもののサイズとする。AとBは木をボトムアップにたどることによって以下のように計算することができる:
A ( S , i ) = | S | + ∑ j ( B ( S ∩ X j , j , i ) − | S ∩ X j | ) {\displaystyle A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\right)}