The absolute center of a network
This paper presents a new algorithm for finding an absolute center (minimax criterion) of an undirected network with n nodes and m arcs based on the concept of minimum-diameter trees. Local centers and their associated radii are identified by a monotonically increasing sequence of lower bounds on the radii. Computational efficiency is addressed in terms of worst-case complexity and practical performance. The complexity of the algorithm is O(n(2) lg n + mn). In practice, because of its very rapid convergence, the algorithm renders the problem amenable even to manual solution for quite large networks, provided that the mini mal-distance matrix is given. Otherwise, evaluation of this matrix is the effective computational bottleneck. An interesting feature of the algorithm and its theoretical foundations is that it synthesizes and generalizes some well-known results in this area, particularly Halpern's lower bound on the local radius of a network and properties of centers of tree networks. (C) 2004 Wiley Periodicals, Inc.
centers networks location