このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は
#noredirect を付けた URL /centroid-decomposition#noredirect を利用してください。
- name
- 重心分解
- short description
- 重心分解とは、木を分解する手法のひとつである。木からその重心を削除することを再帰的に行う。重心の削除のたびに木の大きさが半分以下になる。分解の過程に沿って重心だった頂点の集合に木構造を入れたとき、元々の木の頂点数を $n$ とすると分解されてできた木の高さが $O(\log n)$ になることを特徴とする。
- changelog
-
- 2020年07月09日「見出し作成」 authors: kimiyuki, reviewers:none
- license
This work is licensed under a Creative Commons Attribution 4.0 International License.