Bounded fan-out m-center problem

✍ Scribed by Ho Jan-Ming; Ming-Tat Ko

• Book ID: 104137439
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 548 KB
• Volume: 63
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00104-x

✦ Synopsis

In this paper, we study the bounded fan-out m-center problem. Given a graph G = (y 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 = co) 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 0( n log* n . log m) algorithm for tree networks, where n is the number of vertices. @ 1997 Elsevier Science B.V.