Abstract
Let T = ( V, E ) be a free tree in which each vertex has a weight and each edge has a length. Let n = | V |. Given T and parameters k and l, a ( k, l )-tree core is a subtree X of T with diameter {less-than or slanted equal to}l, having k leaves, which minimizes the sum of the weighted distances from all vertices in T to X. In this paper, two efficient algorithms are presented for finding a ( k, l )-tree core of T. The first algorithm has O ( n 2 ) time complexity for the case that each edge has an arbitrary length. The second algorithm has O ( l k n ) time complexity for the case that the lengths of all edges are 1. The ( k, l )-tree core problem has an application in distributed database systems. © 2005 Elsevier Inc. All rights reserved.