Solving covering problems and the uncapacitated plant location problem on trees

Given a tree network on n vertices, a neighborhood subtree is defined as the set of all points on the tree within a certain radius of a given point, called the center. It is shown that for any two neighborhood subtrees containing the same endpoint of a longest path in the tree one is contained in the other. This result is then used to obtain O(n²) algorithms for the minimum cost covering problem and the minimum cost operating problem as well as an O(n³) algorithm for the uncapacitated plant location problem on the tree.