Abstract
The 1-core of a graph is a path minimizing the sum of the distances of all vertices of the graph from the path. A linear algorithm for finding a 1-core of a tree was presented by Morgan and Slater. The problem for general graphs is NP-Hard. A 2-core of a graph is a set of two paths minimizing the sum of the distances of all vertices of the graph from any of the two paths. We consider both cases of disjoint paths and intersecting paths for a tree. Interesting relations between 1-core and 2-core of a tree are found. These relations imply efficient algorithms for finding the 2-core. The complexity of the algorithms is O(IVI.d(T)) where d(T) is the number of edges in the diameter of the tree. These algorithms are applicable for routing highways in a system of roads. A w-point core is a path minimizing the sum of the distances of all vertices of the graph from either the vertex w or the path. A linear algorithm for finding a w-point core of a tree is presented. It is applied as a procedure for the previous algorithms.