On the interchange heuristic for locating centers and medians in a graph

Ján Plesník

Mathematica Slovaca (1987)

  • Volume: 37, Issue: 2, page 209-216
  • ISSN: 0139-9918

How to cite

top

Plesník, Ján. "On the interchange heuristic for locating centers and medians in a graph." Mathematica Slovaca 37.2 (1987): 209-216. <http://eudml.org/doc/31579>.

@article{Plesník1987,
author = {Plesník, Ján},
journal = {Mathematica Slovaca},
keywords = {graph center; exchange heuristic; hill climbing; weighted distance; p- center problem; p-median problem; k-optimal sets},
language = {eng},
number = {2},
pages = {209-216},
publisher = {Mathematical Institute of the Slovak Academy of Sciences},
title = {On the interchange heuristic for locating centers and medians in a graph},
url = {http://eudml.org/doc/31579},
volume = {37},
year = {1987},
}

TY - JOUR
AU - Plesník, Ján
TI - On the interchange heuristic for locating centers and medians in a graph
JO - Mathematica Slovaca
PY - 1987
PB - Mathematical Institute of the Slovak Academy of Sciences
VL - 37
IS - 2
SP - 209
EP - 216
LA - eng
KW - graph center; exchange heuristic; hill climbing; weighted distance; p- center problem; p-median problem; k-optimal sets
UR - http://eudml.org/doc/31579
ER -

References

top
  1. BEHZAD M., CHARTRAND, G, LESNIAK-FOSTER L., Graphs and Digraphs, Pгindle, Webeг and Schmidt, Boston, 1979. (1979) MR0525578
  2. CHRISTOFIDES N., Graph Theoгy: an algorithmic approach, Academic Press, London, 1975. (1975) MR0429612
  3. HAKIMI S. L., Optimal locations of switching centers and the absolute centers and medians of a graph, Operations Res. 12, 1964, 450-459. (1964) 
  4. HAKIMI S. L., Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Operations Res. 13, 1965, 462-475. (1965) Zbl0135.20501MR0186497
  5. HALPERN J., MAIMON O., Algorithms for the m-center problems; a survey, European J. Operational Res. 10, 1982, 90-99. (1982) Zbl0481.90021MR0655498
  6. HARARY F., Graph Theory, Addison-Wesley, Reading, 1969. (1969) Zbl0196.27202MR0256911
  7. HOCHBAUM D. S., SHMOYS D. B., A best possible heuristic for the k-center problem, Math. Oper. Res. 10, 1985, 180-184. (1985) Zbl0565.90015MR0793876
  8. HOCHBAUM D. S., SHMOYS D. B., Powers of graphs: a powerfull approximation algorithm technique for bottleneck problems, J. Assoc. Comput. Mach. (to appear). 
  9. HSU W. L., NEMHAUSER G. L., Easy and hard bottleneck location problems, Discrete Appl. Math. 1, 1979, 209-215. (1979) Zbl0424.90049MR0549500
  10. JARVINEN P., RAJALA J., SINERVO H., A branch-and-bound algorithm for seeking the p-median, Operations Res. 20,1972, 173-182. (1972) 
  11. 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
  12. KARIV O., HAKIMI S. L., An algorithmic approach to network location problems. II: the p-medians, SIAM J. Appl. Math. 37, 1979, 539-560. (1979) Zbl0432.90075MR0549139
  13. MINIEKA E., Optimization Algorithms for Networks and Graphs, Marcel Dekker, New York, 1978. (1978) Zbl0427.90058MR0517268
  14. MINIEKA E., The centers and medians of a graph, Operations Res. 25, 1977, 641-650. (1977) Zbl0383.90046MR0524906
  15. PLESNIK J., On the computational complexity of centers locating in a graph, Aplikace Mat. 25, 1980, 445-452. (1980) Zbl0454.68026MR0596851
  16. REVELLE C., MARKS D., LIEBMAN J. C., An analysis of private and public sector location models, Management Sci. 16, 1970, 692-707. (1970) Zbl0195.21901
  17. 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
  18. TANSEL B. C, FRANCIS R. L., LOWE T. J., Location on networks: a survey; part II: exploiting tree network structure, Management Sci. 29, 1983. 498-511. (1983) MR0704594
  19. TEITZ M. B., BART B., Heuristic methods for estimating the generalized vertex median of a weighted graph, Operations Res. 16, 1968, 955 -961. (1968) Zbl0165.22804
  20. WONG R. T., Location and network design, In: Combinatorial Optimization: annotated bibliographies. Wiley, New York, 1985, 129- 147. (1985) Zbl0556.90018MR0807391
  21. DYER M. E., FRIEZE A. M., A simple heuristic for the p-centre problem, Oper. Res. Lett. 3, 1985, 285-288. (1985) Zbl0556.90019MR0797340

NotesEmbed ?

top

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.