重心分解

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