On the computational complexity of centers locating in a graph
It is shown that the problem of finding a minimum -basis, the -center problem, and the -median problem are -complete even in the case of such communication networks as planar graphs with maximum degree 3. Moreover, a near optimal -center problem is also -complete.