A new result on the complexity of the p-center problem. (Spanish. English summary) Zbl 0692.90042

Summary: Let G be an undirected graph with n vertices and m edges. A p-center of G is a set of p points that minimizes the distance to the farthest vertex. This minimum is the p-radius. A local center is a point c at the same distance (the range of the local center) to the vertices of a nonempty set which are not all optimally reachable from c through the same adjacent vertex. Every p-radius is the range of a local center so that we only need to find the least range r such that there is a set of p points that covers all the vertices within a distance r. This value of r is the p-radius and the corresponding set is a p-center. By considering the r- extremes (the points that are at distance r from any vertex) it is enough to find these sets. By using r-extremes we give an \(O(m^ p\cdot n^{p+1}\cdot \log n)\) simple algorithm that is experimentally compared with the Handler relaxation algorithm.


90B05 Inventory, storage, reservoirs
90C35 Programming involving graphs or networks
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] AHO, A. V.; HOPCROFT, J. E., y ULLMAN, J. D. (1983):Data Structures and Algorithms, Addison-Wesley. · Zbl 0487.68005
[2] BALAS, E., y HO, A. (1980): “Set Covering Algorithms Using Cutting Planes, Heuristics and Subgradient Optimization: A Computational Study{”,Math. Prog., 12, 37–60.} · Zbl 0435.90074
[3] GONDRAN, M., y MINOUX, M. (1984):Graphs and Algorithms, John Wiley.
[4] HAKIMI, S. L. (1965): “Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph-Theoretic Problems{”,Oper. Res., 13, 462–475.} · Zbl 0135.20501 · doi:10.1287/opre.13.3.462
[5] HANDLER, G. Y. (1979): “Complexity and Efficiency in Minimax Network Location{”,Combinatorial Optimization (N. Christofides y Mingozzi, eds.), New York, John Wiley, 281–325.}
[6] HANDLER, G. Y., y MIRCHANDANI, P. B. (1979):Location on Networks: Theory and Algorithms, Matsachussets, M.I.T. Press. · Zbl 0533.90026
[7] KARIV, O., y HAKIMI, S. L. (1979): “An Algorithmic Approach to Network Location Problems. Part I: Thep-Centers{”,SIAM, J. of App. Math., 37, 3, 513–538.} · Zbl 0432.90074 · doi:10.1137/0137040
[8] MINIEKA, E. (1970): “The m-Center Problem{”,SIAM Review, 12, 138–139.} · Zbl 0193.24204 · doi:10.1137/1012016
[9] MORENO, J. (1985): “A Correction to the Definition of Local Center{”,Eur. J. of Oper. Res., 20, 382–386.} · Zbl 0564.90014 · doi:10.1016/0377-2217(85)90011-6
[10] MORENO, J. (1986):Localización Minimax en Grafos Mixtos, Tesis Doctoral, Universidad Complutense de Madrid.
[11] SYSLO, M. M.; DEO, N., y KOWALIK, J. S. (1983):Discrete Optimization Algorithms with Pascal Programs, New Jersey, Prenticel-Hall. · Zbl 1113.90105
[12] TAMIR, A. (1987): “Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures{”, Presentado a ISOLDE IV, Namur, Bélgica.}
[13] TARJAN, R. E. (1983):Data Structures and Network Algorithms, New Jersey, Society for Industrial and Applied Mathematics. · Zbl 0584.68077
[14] VASKO, F. J., y WILSON, G. R. (1984): “An Efficient Heuristic for Large Set Covering Problems{”,Naval Research Logistic Quarterly, 31, 163–171.} · Zbl 0534.90064 · doi:10.1002/nav.3800310118
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.