Article
MSC:
68C25,
68E10,
68Q25,
68R10,
90B05,
94C15 | MR 0596851 | Zbl 0454.68026 | DOI: 10.21136/AM.1980.103883
Full entry |
PDF
(1.0 MB)
Feedback
PDF
(1.0 MB)
Feedback
Keywords:
$p$-median problem; $NP$-complete; communication networks; $m$-center problem
$p$-median problem; $NP$-complete; communication networks; $m$-center problem
Summary:
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.
References:
[1] N. Christofides: Graph theory- an algorithmic approach. Academic Press, New York 1975. MR 0429612 | Zbl 0321.94011
[2] H. Frank I. T. Frisch: Communication, transmission, and transportation networks. Addison-Wesley, Reading 1971. MR 0347343
[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 0468310
[4] M. R. Garey D. S. Johnson: The complexity of near-optimal graph coloring. J. Assoc. Соmр. Mach. 23 (1976), 43-49. DOI 10.1145/321921.321926 | MR 0426496
[5] M. R. Garey D. S. Johnson: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32 (1977), 826-834. DOI 10.1137/0132071 | MR 0443426
[6] M. R. Garey D. S. Johnson L. Stockmeyer: Some simplified NP-complete graph problems. Theoretical Comput. Sci. 1 (1976), 237-267. DOI 10.1016/0304-3975(76)90059-1 | MR 0411240
[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 10.1137/0205049 | MR 0444516
[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 10.1287/opre.12.3.450 | Zbl 0123.00305
[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 10.1287/opre.13.3.462 | MR 0186497
[10] S. L. Hakimi E. F. Schmeichel J. G. Pierce: Оn p-centers in networks. Transportation Sci. 12 (1978), 1 - 15. DOI 10.1287/trsc.12.1.1 | MR 0506674
[11] R. M. Karp: On the computational complexity of combinatorial problems. Networks 5 (1975), 45-68. DOI 10.1002/net.1975.5.1.45 | Zbl 0324.05003
[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 0278712
[13] E. Minieka: The centers and medians of a graph. Operations Res. 25 (1977), 641 - 650. DOI 10.1287/opre.25.4.641 | MR 0524906 | Zbl 0383.90046
[14] S. C. Narula U. I. Оgbu H. M. Samuelsson: An algorithm for the p-median problem. Operations Res. 25 (1977), 709-713. DOI 10.1287/opre.25.4.709 | MR 0446532
[15] S. Sahni T. Gonzales: P-complete approximation problems. J. Assoc. Соmр. Mach. 23 (1976), 555-565. DOI 10.1145/321958.321975 | MR 0408313
[16] P. J. Slater: R-domination in graphs. J. Assoc. Сотр. Mach. 23 (1976), 445-450. MR 0449602 | Zbl 0349.05120
Search
Partner of
