Consider a finite, undirected tree graph with n vertices and its associated shortest path distance matrix D of dimension n. This paper studies the problem of selecting a subset of size p of the column indices (vertices) of D such that the smallest row sum in the resulting n×p submatrix is as large as possible. In particular, the paper characterizes the optimal solutions for p=2,3, and 4 and identifies certain characteristics of solutions for p≥4 which complicate the search for an optimal solution. A constructive heuristic is developed and its performance is evaluated for p=5 and p=10 on randomly generated trees each with 25 vertices.
