Algorithms for a k-tree core of a tree

The authors define a generalization of a core which they call a k-tree core. Given a tree T and parameter k, a k-tree core is a subtree T´ of T containing exactly k leaves that minimizes d(T´)=Σ_υ∈V(T)d (υ, T´), where d(υ, T´) is the distance from vertex υ to subtree T´. They then give two algorithms to find a k-tree core of a tree with n vertices. The complexities of these algorithms are O(kn) and O (n lg n) respectively. This work is motivated by a resource allocation problem dealing with a partially replicated distributed database defined on a tree network