ALGORITHMIC APPROACH TO NETWORK LOCATION PROBLEMS .1. P-CENTERS

Problems of finding p-centers and dominating sets of radius r in networks are discussed. Let n be the number of vertices and vertical E vertical be the number of edges of a network. With the assumption that the distance-matrix of the network is available, there are designed an O( vertical E vertical multiplied by (times) n multiplied by (times) lg n) algorithm for finding an absolute l-center of a vertex-weighted network and an O( vertical E vertical multiplied by (times) n plus n**2 multiplied by (times) lg n) algorithm for finding an absolute 1-center of a vertex-unweighted network. It is shown that the problem of finding a (vertex or absolute) p-center (for 1 less than p less than n) of a (vertex-weighted or vertex-unweighted) network, and the problem of finding a dominating set of radius r are NP-hard even in the case where the network has a simple structure.