An Algorithmic Approach to Network Location Problems. I: Thep-Centers

Problems of finding p-centers and dominating sets of radius r in networks are discussed in this paper. Let n be the number of vertices and | E | be the number of edges of a network. With the assumption that the distance-matrix of the network is available, we design an O (| E | n n) algorithm for finding an absolute 1-center of a vertex-weighted network and an O (| E | n + n² n) algorithm for finding an absolute 1-center of a vertex-unweighted network (the problem of finding a vertex 1-center of a network is trivial). We show that the problem of finding a (vertex or absolute) p-center (for 1 < p < 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 (e. g. , a planar graph of maximum vertex degree 3). However, we describe an algorithm of complexity O (| E |ᵖ n^{2p - 1 / (p - 1) !) n} (respectively, O| E |ᵖ n^{2p - 1 / (p - 1) !} for finding an absolute p-center in a vertex-weighted (respectively, vertex-unweighted) network. We proceed by discussing the problems of finding p-centers and dominating sets of networks whose underlying graphs are trees. When the network is a vertex-weighted tree, we obtain the following algorithms: An O (n n) algorithm for finding the (vertex or absolute) 1-center; an O (n) algorithm for finding a (vertex or absolute) dominating set of radius r; an O (n² n) algorithm for finding a (vertex or absolute) p-center for any 1 < p < n. Some generalizations of these problems are discussed. When the network is a vertex-unweighted tree, O (n) algorithms for finding the (vertex or absolute) 1-center and an absolute 2-center are already known; we extend these results by giving an O (n ^p - 2 n) algorithm for finding an absolute p-center (where 3 p < n) and an O (n ^p - 1 n) algorithm for finding a vertex p-center (where 2 p < n). In part II we treat the p-median problem.