Geodesic
On the computational complexity of centers locating in a graph
Applications of Mathematics, Tome 25 (1980) no. 6, pp. 445-452
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/AM.1980.103883
Classification : 68C25, 68E10, 68Q25, 68R10, 90B05, 94C15
Keywords: $p$-median problem; $NP$-complete; communication networks; $m$-center problem 
@article{10_21136_AM_1980_103883,
     author = {Plesn{\'\i}k, J\'an},
     title = {On the computational complexity of centers locating in a graph},
     journal = {Applications of Mathematics},
     pages = {445--452},
     year = {1980},
     volume = {25},
     number = {6},
     doi = {10.21136/AM.1980.103883},
     mrnumber = {0596851},
     zbl = {0454.68026},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1980.103883/}
}
TY  - JOUR
AU  - Plesník, Ján
TI  - On the computational complexity of centers locating in a graph
JO  - Applications of Mathematics
PY  - 1980
SP  - 445
EP  - 452
VL  - 25
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1980.103883/
DO  - 10.21136/AM.1980.103883
LA  - en
ID  - 10_21136_AM_1980_103883
ER  - 
%0 Journal Article
%A Plesník, Ján
%T On the computational complexity of centers locating in a graph
%J Applications of Mathematics
%D 1980
%P 445-452
%V 25
%N 6
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1980.103883/
%R 10.21136/AM.1980.103883
%G en
%F 10_21136_AM_1980_103883
Plesník, Ján. On the computational complexity of centers locating in a graph. Applications of Mathematics, Tome 25 (1980) no. 6, pp. 445-452. doi: 10.21136/AM.1980.103883

[1] N. Christofides: Graph theory- an algorithmic approach. Academic Press, New York 1975. | MR | Zbl

[2] H. Frank I. T. Frisch: Communication, transmission, and transportation networks. Addison-Wesley, Reading 1971. | MR

[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. | MR

[4] M. R. Garey D. S. Johnson: The complexity of near-optimal graph coloring. J. Assoc. Соmр. Mach. 23 (1976), 43-49. | DOI | MR

[5] M. R. Garey D. S. Johnson: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32 (1977), 826-834. | DOI | MR

[6] M. R. Garey D. S. Johnson L. Stockmeyer: Some simplified NP-complete graph problems. Theoretical Comput. Sci. 1 (1976), 237-267. | DOI | MR

[7] M. R. Garey D. S. Johnson R. E. Tarjan: The planar hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5 (1976), 704-714. | DOI | MR

[8] S. L. Hakimi: Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Res. 12 (1964), 450-459. | DOI | Zbl

[9] S. L. Hakimi: Optimum distribution of switching centers in a communications network and some related graph theoretic problems. Operations Res. 13 (1965), 462-475. | DOI | MR

[10] S. L. Hakimi E. F. Schmeichel J. G. Pierce: Оn p-centers in networks. Transportation Sci. 12 (1978), 1 - 15. | DOI | MR

[11] R. M. Karp: On the computational complexity of combinatorial problems. Networks 5 (1975), 45-68. | DOI | Zbl

[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. | MR

[13] E. Minieka: The centers and medians of a graph. Operations Res. 25 (1977), 641 - 650. | DOI | MR | Zbl

[14] S. C. Narula U. I. Оgbu H. M. Samuelsson: An algorithm for the p-median problem. Operations Res. 25 (1977), 709-713. | DOI | MR

[15] S. Sahni T. Gonzales: P-complete approximation problems. J. Assoc. Соmр. Mach. 23 (1976), 555-565. | DOI | MR

[16] P. J. Slater: R-domination in graphs. J. Assoc. Сотр. Mach. 23 (1976), 445-450. | MR | Zbl

Cité par Sources :