On p-Centers in Networks

This paper presents some improvements and some generalizations of existing techniques for computing a 1-center of a network and a p-center of a tree. For a network with n vertices and |E| edges the amount of computation to find a 1-center is shown to be at most 0(|E|n 2 log n) in the vertex weighted case and 0(|E|n log n) in the vertex unweighted; for a p-center of a tree (p > 1, unweighted case), the bound is 0(n p−1 ).