A Linear Tree Partitioning Algorithm
Sukhamay Kundu, Jayadev Misra · SIAM Journal on Computing · 1977
Given a rooted tree with a positive weight associated with every node, a linear algorithm is presented that will partition the tree into a minimum number of subtrees such that the sum of node weights in no subtree exceed a prespecified value k.