On the computational complexity of centers locating in a graph
Ján Plesnı́k · Applications of Mathematics · 1980
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.