Two heuristics for the absolute p -center problem in graphs

Ján Plesník

Mathematica Slovaca (1988)

  • Volume: 38, Issue: 3, page 227-233
  • ISSN: 0139-9918

How to cite


Plesník, Ján. "Two heuristics for the absolute $p$-center problem in graphs." Mathematica Slovaca 38.3 (1988): 227-233. <>.

author = {Plesník, Ján},
journal = {Mathematica Slovaca},
keywords = {weighted vertices; weighted edges; absolute p-center problem; weighted eccentricity},
language = {eng},
number = {3},
pages = {227-233},
publisher = {Mathematical Institute of the Slovak Academy of Sciences},
title = {Two heuristics for the absolute $p$-center problem in graphs},
url = {},
volume = {38},
year = {1988},

AU - Plesník, Ján
TI - Two heuristics for the absolute $p$-center problem in graphs
JO - Mathematica Slovaca
PY - 1988
PB - Mathematical Institute of the Slovak Academy of Sciences
VL - 38
IS - 3
SP - 227
EP - 233
LA - eng
KW - weighted vertices; weighted edges; absolute p-center problem; weighted eccentricity
UR -
ER -


  1. CHRISTOFIDES N., Graрh Theory: an Algorithmic Approach, Academic Press, London, 1975. (1975) MR0429612
  2. DYER M. E., FRIEZE A. M., A simple heuristic for the p-centre problem, J. Oper. Res. Soc. 35, 1984, 285-288. (1984) MR0797340
  3. GAREY M. R., JOHNSON D. S., Computers and Intractability: a Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. (1979) Zbl0411.68039MR0519066
  4. HAKIMI S. L., Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Res. 12, 1964, 450-459. (1964) Zbl0123.00305
  5. HOCHBAUM D. S., SHMOYS D. B., A best possible heuristic for the k-center problem, Math. Opeг. Res. 10, 1985, 180-184. (1985) Zbl0565.90015MR0793876
  6. HOCHBAUM D. S., SHMOYS D. B., A unified approach to approximation algorithms for bottleneck problems, J. Assoc. Comput. Mach. 33, 1986, 533-550. (1986) MR0849028
  7. HSU W. L., NEMHAUSER G. L., Easy and hard bottleneck location problems, Discrete Appl. Math. 1, 1979, 209-215. (1979) Zbl0424.90049MR0549500
  8. KARIV O., HAKIMI S. L., An algorithmic approach to network location problems I: the p-centers, SIAM J. Appl. Math. 37, 1979, 513-538. (1979) Zbl0432.90074MR0549138
  9. MINIEKA E., The centeгs and medians of a gгaph, Opeгations Res. 25, 1977, 641-650. (1977) MR0524906
  10. PLESNÍK J., On the computational complexity of centers locating in a graph, Aplikace Mat. 25, 1980, 445-452. (1980) Zbl0454.68026MR0596851
  11. PLESNÍK J., A heuristic for thep-center problem in graphs, Discrete Appl. Math. 17, 1987, 263-268. (1987) MR0890636
  12. PLESNÍK J., On the interchange heuristic for locating centers and medians in a graph, Math. Slovaca, 37, 1987, 209-216. (1987) Zbl0642.05030MR0899438
  13. 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, 1983, 482-497. (1983) MR0704593
  14. WONG R. T., Location and netwoгk design, In: Combinatorial Optimization: Annotated Bibliographies (M. O'hEigeaгtaigh, J. K. Lenstra and A. H. G. Rinnooy Kan, eds.), Wiley, New York, 1985, 129-147. (1985) MR0807391

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.