Bounded fan-out m-center problem

In this paper, we study the bounded fan-out m-center problem. Given a graph G = (V, E), positive integers m and B, the problem is to find the location of m centers to service all the vertices so as to minimize the maximum service radius subject to the constraint that each center is allowed to service no more than B vertices. Note that the centers can be located either on a vertex or an edge. It is well known that the m-center problem without fan-out bound (B = ∞) is NP-complete for general graphs, Euclidean geometry, and rectilinear metric geometry. The same is also true for the bounded fan-out m-center problem. In this paper, we present an O(n log2 n · log m) algorithm for tree networks, where n is the number of vertices.