木分解
B ( S , i , j ) = max S ′ ⊂ X i S = S ′ ∩ X j A ( S ′ , i ) {\displaystyle B(S,i,j)=\max _{S'\subset X_{i} \atop S=S'\cap X_{j}}A(S',i)}
ここで、 A ( S , i ) {\displaystyle A(S,i)} の式における和は X i {\displaystyle X_{i}} の子ノード全体をわたる。
各ノードと辺において、A(S,i)やB(S,i,j)を計算すべき集合Sの個数は高々2である。そのため、kが定数ならば、1ノードおよび1辺あたりの計算は定数時間でできる。最大独立集合の大きさは根のノードに格納されている最大の値であり、最大独立集合自身も(普通の動的計画法のアルゴリズムのように)最大値からバックトラックを行うことで計算できる。そのため、決められた木幅のグラフの最大独立集合問題は線形時間で解ける。類似のアルゴリズムによって、他の多くのグラフの問題を解くことができる。
この動的計画法によるアプローチは、機械学習において、決められた木幅のグラフにおける確率伝搬法を行うen:junction tree algorithmに用いられる。また木幅を計算し木分解を構成するためにも用いられる。典型的には、そのようなアルゴリズムは最初に木幅を近似し、その近似した木幅の木分解を構成し、次にその木分解の上で動的計画法を行うことで正確な木幅を計算する。