Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Heavy-light decomposition
open-in-new
<p>In <a href="/facts/Combinatorics/k14xUoKT">combinatorial mathematics</a> and <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, heavy-light decomposition (also called heavy path decomposition) is a technique for decomposing a <a href="/facts/Tree_(graph_theory)/TCWk4Joy">rooted tree</a> into a set of <a href="/facts/Path_(graph_theory)/WMsq21Nf">paths</a>. In a heavy path decomposition, each non-leaf node selects one "heavy edge", the edge to the child that has the greatest number of descendants (breaking ties arbitrarily). The selected edges form the paths of the decomposition. </p>