今回は木幅(tree-width)の話を書いてみようと思います。 木幅とは、大雑把に言うとグラフがどれだけ木に近いかを表す値です(木に近いほど小さな値になります)。NP困難な問題でもグラフを木に限定すると多項式時間で解けたりする話は有名ですが、実は一部…
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。