Facility location on a tree with maximum distance constraints

The problem is to find the minimum number of feasible locations for identical facilities in a tree network when each demand point requires a facility within a specified distance limit and each facility itself requires another facility within a certain proximity. The authors initially develop a tree-reducing procedure that eliminates some demand points on the basis of their facility requirements. Our location procedure then identifies the minimum number of facility sites in the reduced tree. The computational complexity of either procedure is linear in the number of demand points.