このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は
#noredirect
を付けた URL /centroid-decomposition#noredirect を利用してください。
- name
- 重心分解
- short description
- 重心分解とは、木を分解する手法のひとつである。木からその重心を削除することを再帰的に行う。重心の削除のたびに木の大きさが半分以下になる。分解の過程に沿って重心だった頂点の集合に木構造を入れたとき、元々の木の頂点数を $n$ とすると分解されてできた木の高さが $O(\log n)$ になることを特徴とする。