Talk:Heavy-light decomposition
(Redirected from Talk:Heavy path decomposition)
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Does each non-leaf node have a heavy child?
[edit]Perhaps interestingly, these first two publications that use heavy path decompositions, do not define them in the same way.
While, on one hand, one may as well take the heaviest child to be the heavy child breaking ties arbitrarily, one may also just say that a child is heavy if its weight is at least half of one's own.
In Sleator&Tarjan's link-cut-trees, they take the second definition. See e.g. figure 2 on page 368, or the nuts and bolts definition on page 370 under "analysis of expose".
Regardless of their differences, both definitions of course have in common that the light depth of a node cannot exceed the logarithm of n. :) Vuniu (talk) 19:51, 8 January 2023 (UTC)