A heuristic for the p-center problem in graphs. (English) Zbl 0637.05020

The author gives an algorithm of \(O(n^ 2\log n)\) running time with a worst-case error ratio of 2 for the p-centerproblem in a connected graph of n nodes and m edges with edge lengths and vertex weights. A slight modification of the algorithm provides a ratio 2 also for the absolute p- center problem with running time \(O(mn^ 2\log n)\). Both heuristics are best possible.
Reviewer: H.T.Lau


05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Christofides, N., Graph theory: an algorithmic approach, (1975), Academic Press London · Zbl 0321.94011
[2] Drezner, Z., The p-centre problem - heuristic and optimal algorithms, J. oper. res. soc., 35, 741-748, (1984) · Zbl 0544.90024
[3] Dyer, M.E.; Frieze, A.M., A simple heuristic for the p-centre problem, Oper. res. lett., 3, 285-288, (1985) · Zbl 0556.90019
[4] Fowler, R.J.; Paterson, M.S.; Tanimoto, S.L., Optimal packing and covering in the plane are NP-complete, Inform. process. lett., 12, 133-137, (1981) · Zbl 0469.68053
[5] Hakimi, S.L., Optimum locations of switching centers and the absolute centers and medians of a graph, Operations res., 12, 450-459, (1964) · Zbl 0123.00305
[6] Hakini, S.L., Optimal distribution of switching centers in a communications network and some related graph-theoretic problems, Operations res., 13, 462-475, (1965) · Zbl 0135.20501
[7] Hochbaum, D.S.; Shmoys, D.B., A best possible heuristic for the k-center problem, Math. oper. res., 10, 180-184, (1985) · Zbl 0565.90015
[8] D.S. Hochbaum and D.B. Shmoys, Powers of graphs: a powerful approximation algorithm technique for bottleneck problems, J. Assoc. Comput. Mach., to appear.
[9] Hsu, W.L.; Nemhauser, G.I., Easy and hard bottleneck location problems, Discrete appl. math., 1, 209-215, (1979) · Zbl 0424.90049
[10] Johnson, D.B., Efficient algorithms for shortest paths in sparse networks, J. assoc. comput. Mach., 24, 1-13, (1977) · Zbl 0343.68028
[11] Kariv, O.; Hakimi, S.L., An algorithmic approach to network location problems I: the p-centers, SIAM J. appl. math., 37, 513-538, (1979) · Zbl 0432.90074
[12] Masuyama, S.; Ibaraki, T.; Hasegawa, T., The computational complexity of the m-centre problems on the plane, Trans. IECE Japan, E64, 57-64, (1981)
[13] Megiddo, N.; Supowit, K.J., On the complexity of some common geometric location problems, SIAM J. comput., 18, 182-196, (1984) · Zbl 0534.68032
[14] Minieka, E., The centers and medians of a graph, Operations res., 25, 641-650, (1977) · Zbl 0383.90046
[15] Plesnik, J., On the computational complexity of centers locating in a graph, Aplikace mat., 25, 445-452, (1980) · Zbl 0454.68026
[16] Tansel, B.C.; Francis, R.L.; Lowe, T.J., Location on networks: a survey; part I: the p-center and p-Median problems, Management sci., 29, 482-497, (1983) · Zbl 0513.90022
[17] Tansel, B.C.; Francis, R.L.; Lowe, T.J., Location on networks: a survey; part II: exploiting tree network structure, Management sci., 29, 498-511, (1983) · Zbl 0513.90023
[18] Wong, R.T., Location and network design, (), 129-147 · Zbl 0556.90018
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.