ALGORITHMS FOR A CORE AND K-TREE CORE OF A TREE

We first give a one-pass algorithm for finding the core of a tree. This algorithm is a refinement of the two-pass algorithm of Morgan and Slater. We then define a generalization of a core which we 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 ∈ V(T)d(v, T’), where d(v, T’) is the distance from vertex v to subtree T’. We 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. This problem is briefly described in the last section of the paper. © 1993 Academic Press, Inc.