Centroid Decomposition
AlgorithmsHardDecompose tree topologies recursively into logarithmic height centroid trees.
Alt+Shift+C
Configuration Panel
Decompose the tree recursively. The root centroid of the first recursion split is highlighted in yellow.
Tree Layout Canvas
Double-click empty canvas to create root, select node to add child or delete.
Time Complexity
O(N log N) decomposition
Auxiliary Space Complexity
O(N) decomposition structures
Conceptual Overview
Centroid Decomposition is a divide-and-conquer technique on trees. It divides a tree of size N into subtrees of size at most N/2 by removing a special node called the Centroid. The centroid tree structure is obtained by recursively linking centroids.
Algorithm Mechanism
Compute component size. Find centroid node u where all subtrees connected to u have sizes <= N/2. Remove u, link it as parent in the centroid tree, and recursively decompose remaining components.
Source: CP-Algorithms reference guide