Geodesic
On the computational complexity of centers locating in a graph
Applications of Mathematics, Tome 25 (1980) no. 6, pp. 445-452.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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},
     publisher = {mathdoc},
     volume = {25},
     number = {6},
     year = {1980},
     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
PB  - mathdoc
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
%I mathdoc
%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. http://geodesic.mathdoc.fr/articles/10.21136/AM.1980.103883/

Cité par Sources :