<p>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$:</p>

<p><a href="https://eccc.weizmann.ac.il/report/2011/128/" rel="nofollow noreferrer">https://eccc.weizmann.ac.il/report/2011/128/</a></p>

<p>Another nice $TC^0$-decomposition is based on so-called TSLPs in the paper "A Universal Tree Balancing Theorem" (Ganardi, Lohrey):</p>

<p><a href="https://arxiv.org/pdf/1704.08705.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1704.08705.pdf</a></p>

CC BY-SA 3.0
2017-10-19T08:16:06.400Z
2017-10-19T08:16:06.400Z
Danny
<p>The only techniques i know are those in the title.</p>

CC BY-SA 3.0
2017-10-19T07:26:24.767Z
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.
sbzk
<ds.algorithms><graph-algorithms><tree><dynamic-algorithms>
What are some techniques for "balancing" a tree beside heavy-light and centroid decomposition?
GEP
# What are some techniques for "balancing" a tree beside heavy-light and centroid decomposition?

(Asked by: username_0 on 2017-10-19)

The only techniques i know are those in the title.

**Tags:** ds.algorithms, graph-algorithms, tree, dynamic-algorithms

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2017-10-19. Score: 2 | Accepted answer

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):

<https://arxiv.org/pdf/1704.08705.pdf>


---

