On the computational complexity of centers locating in a graph

Ján Plesník

Aplikace matematiky (1980)

  • Volume: 25, Issue: 6, page 445-452
  • ISSN: 0862-7940

Abstract

top
It is shown that the problem of finding a minimum k -basis, the n -center problem, and the p -median problem are N P -complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal m -center problem is also N P -complete.

How to cite

top

Plesník, Ján. "On the computational complexity of centers locating in a graph." Aplikace matematiky 25.6 (1980): 445-452. <http://eudml.org/doc/15171>.

@article{Plesník1980,
abstract = {It is shown that the problem of finding a minimum $k$-basis, the $n$-center problem, and the $p$-median problem are $NP$-complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal $m$-center problem is also $NP$-complete.},
author = {Plesník, Ján},
journal = {Aplikace matematiky},
keywords = {$p$-median problem; $NP$-complete; communication networks; $m$-center problem; p-median problem; NP-complete; communication networks; m-center problem},
language = {eng},
number = {6},
pages = {445-452},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On the computational complexity of centers locating in a graph},
url = {http://eudml.org/doc/15171},
volume = {25},
year = {1980},
}

TY - JOUR
AU - Plesník, Ján
TI - On the computational complexity of centers locating in a graph
JO - Aplikace matematiky
PY - 1980
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 25
IS - 6
SP - 445
EP - 452
AB - It is shown that the problem of finding a minimum $k$-basis, the $n$-center problem, and the $p$-median problem are $NP$-complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal $m$-center problem is also $NP$-complete.
LA - eng
KW - $p$-median problem; $NP$-complete; communication networks; $m$-center problem; p-median problem; NP-complete; communication networks; m-center problem
UR - http://eudml.org/doc/15171
ER -

References

top
  1. N. Christofides, Graph theory- an algorithmic approach, Academic Press, New York 1975. (1975) Zbl0321.94011MR0429612
  2. H. Frank I. T. Frisch, Communication, transmission, and transportation networks, Addison-Wesley, Reading 1971. (1971) MR0347343
  3. M. R. Garey R. L. Graham D. S. Johnson, Some NP-complete geometric problems, Proc. of the 8-th ACM Symposium on Theory of computing. 1976, pp. 10-22. (1976) MR0468310
  4. M. R. Garey D. S. Johnson, 10.1145/321921.321926, J. Assoc. Соmр. Mach. 23 (1976), 43-49. (1976) MR0426496DOI10.1145/321921.321926
  5. M. R. Garey D. S. Johnson, 10.1137/0132071, SIAM J. Appl. Math. 32 (1977), 826-834. (1977) MR0443426DOI10.1137/0132071
  6. M. R. Garey D. S. Johnson L. Stockmeyer, 10.1016/0304-3975(76)90059-1, Theoretical Comput. Sci. 1 (1976), 237-267. (1976) MR0411240DOI10.1016/0304-3975(76)90059-1
  7. M. R. Garey D. S. Johnson R. E. Tarjan, 10.1137/0205049, SIAM J. Comput. 5 (1976), 704-714. (1976) MR0444516DOI10.1137/0205049
  8. S. L. Hakimi, 10.1287/opre.12.3.450, Operations Res. 12 (1964), 450-459. (1964) Zbl0123.00305DOI10.1287/opre.12.3.450
  9. S. L. Hakimi, 10.1287/opre.13.3.462, Operations Res. 13 (1965), 462-475. (1965) MR0186497DOI10.1287/opre.13.3.462
  10. S. L. Hakimi E. F. Schmeichel J. G. Pierce, 10.1287/trsc.12.1.1, Transportation Sci. 12 (1978), 1 - 15. (1978) MR0506674DOI10.1287/trsc.12.1.1
  11. R. M. Karp, 10.1002/net.1975.5.1.45, Networks 5 (1975), 45-68. (1975) Zbl0324.05003DOI10.1002/net.1975.5.1.45
  12. M. Koman, Solution of one variant of the location problem by the graph theory, (Czech). Matematika (geometrie a teorie grafů). Sborník Pedagogické fakulty University Karlovy, Prague 1970, 93-103. (1970) MR0278712
  13. E. Minieka, 10.1287/opre.25.4.641, Operations Res. 25 (1977), 641 - 650. (1977) Zbl0383.90046MR0524906DOI10.1287/opre.25.4.641
  14. S. C. Narula U. I. Оgbu H. M. Samuelsson, 10.1287/opre.25.4.709, Operations Res. 25 (1977), 709-713. (1977) MR0446532DOI10.1287/opre.25.4.709
  15. S. Sahni T. Gonzales, 10.1145/321958.321975, J. Assoc. Соmр. Mach. 23 (1976), 555-565. (1976) MR0408313DOI10.1145/321958.321975
  16. P. J. Slater, R-domination in graphs, J. Assoc. Сотр. Mach. 23 (1976), 445-450. (1976) Zbl0349.05120MR0449602

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.