×

On the computational complexity of centers locating in a graph. (English) Zbl 0454.68026


MSC:

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] N. Christofides: Graph theory- an algorithmic approach. Academic Press, New York 1975. · Zbl 0321.94011
[2] H. Frank I. T. Frisch: Communication, transmission, and transportation networks. Addison-Wesley, Reading 1971. · Zbl 0281.94012
[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. · Zbl 0377.68036
[4] M. R. Garey D. S. Johnson: The complexity of near-optimal graph coloring. J. Assoc. Comp. Mach. 23 (1976), 43-49. · Zbl 0322.05111 · doi:10.1145/321921.321926
[5] M. R. Garey D. S. Johnson: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32 (1977), 826-834. · Zbl 0396.05009 · doi:10.1137/0132071
[6] M. R. Garey D. S. Johnson L. Stockmeyer: Some simplified NP-complete graph problems. Theoretical Comput. Sci. 1 (1976), 237-267. · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[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. · Zbl 0346.05110 · doi:10.1137/0205049
[8] S. L. Hakimi: Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Res. 12 (1964), 450-459. · Zbl 0123.00305 · doi:10.1287/opre.12.3.450
[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. · Zbl 0135.20501 · doi:10.1287/opre.13.3.462
[10] S. L. Hakimi E. F. Schmeichel J. G. Pierce: On p-centers in networks. Transportation Sci. 12 (1978), 1 - 15. · doi:10.1287/trsc.12.1.1
[11] R. M. Karp: On the computational complexity of combinatorial problems. Networks 5 (1975), 45-68. · 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.
[13] E. Minieka: The centers and medians of a graph. Operations Res. 25 (1977), 641 - 650. · Zbl 0383.90046 · doi:10.1287/opre.25.4.641
[14] S. C. Narula U. I. Ogbu H. M. Samuelsson: An algorithm for the p-median problem. Operations Res. 25 (1977), 709-713. · Zbl 0372.90096 · doi:10.1287/opre.25.4.709
[15] S. Sahni T. Gonzales: P-complete approximation problems. J. Assoc. Comp. Mach. 23 (1976), 555-565. · Zbl 0348.90152 · doi:10.1145/321958.321975
[16] P. J. Slater: R-domination in graphs. J. Assoc. Cotp. Mach. 23 (1976), 445-450. · Zbl 0349.05120 · doi:10.1145/321958.321964
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.