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. In this paper, an O(n) time algorithm is proposed for the case p = 2, where n is the number of vertices in T. Our algorithm improves the two O(n 2 ) time algorithms previously proposed by Becker and Perl [Discrete Appl. Math., 11 (1985), pp. 103-113]. With some modifications, the proposed algorithm can be implemented on the EREW PRAM in O(log 2 n) time using O(n log n) work.