An Algorithmic Approach to Network Location Problems. I: The<i>p</i>-Centers

Abstract

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 | \cdot n \cdot \lg n)$ algorithm for finding an absolute 1-center of a vertex-weighted network and an $O(| E | \cdot n + n^2 \cdot \lg 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 |^p \cdot n^{2p - 1} / (p - 1)! ) \lg n]}$ (respectively, ${O[| E |^p \cdot 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 \cdot \lg 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^2 \cdot \lg 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 \cdot \lg ^{p - 2} n)$ algorithm for finding an absolute p-center (where $3 \leqq p < n$) and an $O(n \cdot \lg ^{p - 1} n)$ algorithm for finding a vertex p-center (where $2 \leqq p < n$). In part II we treat the p-median problem.