Finding Two-Centers of a Tree: The Continuous Case

Abstract

An efficient algorithm for finding the absolute single-center (minimax-distance criterion) of a tree is extended to the location of two-centers, where these may be located anywhere on the continuum of points defined by the tree network. A graph-theoretic analysis transforms this bivariate problem into three unwariaie single-center problems. The resultant algorithm, whose complexity is a linear function of the number of nodes, requires an additional effort of about 25% over the single-center algorithm to locate an optimal pair of venters. Two varieties of the problem are considered; in the first, demand for service can occur anywhere on the network; in the second, demand is restricted to the set of nodes.