On <i>p</i>-Centers in Networks

Abstract

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 &gt; 1, unweighted case), the bound is 0(n p−1 ).