The only techniques i know are those in the title.
1
-
1$\begingroup$ Balancing may not be the correct term, balancing refers to AVL, Red Black, Splay tree like structures. You seem to be looking at decomposition. What kind of decomposition are u interested in. Look for Topology Trees, Top Trees, Euler Tour Trees, Sleator Tarjan Trees (uses heavy light decomposition) for several similar decomposition. $\endgroup$– sbzkOct 19, 2017 at 7:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The paper "Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth" (Elberfeld, Jacobi, Tantau) gives a nice balanced tree decomposition based on tree contraction in $TC^0$:
https://eccc.weizmann.ac.il/report/2011/128/
Another nice $TC^0$-decomposition is based on so-called TSLPs in the paper "A Universal Tree Balancing Theorem" (Ganardi, Lohrey):
