Abstract
Let T be an edge-weighted tree. A p-core of T is a set of p mutually disjoint paths in T that minimizes the sum of the distances of all vertices in T from any of the p paths, where p ≥ 1 is an integer. Let n be the number of vertices in T. In this paper, an O(n) time algorithm is proposed for the case p=2. Applying our 2-core algorithm as a procedure, we also show that the p-core problem can be solved in O(n p-1 ) time for any constant p ≥ 2.