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 |ᵖ · n2p - 1 / (p - 1)! ) n] (respectively, O[| E |ᵖ · n2p - 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.