| Title:
|
On the computational complexity of centers locating in a graph (English) |
| Author:
|
Plesník, Ján |
| Language:
|
English |
| Journal:
|
Aplikace matematiky |
| ISSN:
|
0373-6725 |
| Volume:
|
25 |
| Issue:
|
6 |
| Year:
|
1980 |
| Pages:
|
445-452 |
| Summary lang:
|
English |
| Summary lang:
|
Slovak |
| Summary lang:
|
Russian |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
$p$-median problem |
| Keyword:
|
$NP$-complete |
| Keyword:
|
communication networks |
| Keyword:
|
$m$-center problem |
| MSC:
|
68C25 |
| MSC:
|
68E10 |
| MSC:
|
68Q25 |
| MSC:
|
68R10 |
| MSC:
|
90B05 |
| MSC:
|
94C15 |
| idZBL:
|
Zbl 0454.68026 |
| idMR:
|
MR0596851 |
| DOI:
|
10.21136/AM.1980.103883 |
| . |
| Date available:
|
2008-05-20T18:15:41Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/103883 |
| . |
| Reference:
|
[1] N. Christofides: Graph theory- an algorithmic approach.Academic Press, New York 1975. Zbl 0321.94011, MR 0429612 |
| Reference:
|
[2] H. Frank I. T. Frisch: Communication, transmission, and transportation networks.Addison-Wesley, Reading 1971. MR 0347343 |
| Reference:
|
[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 |
| Reference:
|
[4] M. R. Garey D. S. Johnson: The complexity of near-optimal graph coloring.J. Assoc. Соmр. Mach. 23 (1976), 43-49. MR 0426496, 10.1145/321921.321926 |
| Reference:
|
[5] M. R. Garey D. S. Johnson: The rectilinear Steiner tree problem is NP-complete.SIAM J. Appl. Math. 32 (1977), 826-834. MR 0443426, 10.1137/0132071 |
| Reference:
|
[6] M. R. Garey D. S. Johnson L. Stockmeyer: Some simplified NP-complete graph problems.Theoretical Comput. Sci. 1 (1976), 237-267. MR 0411240, 10.1016/0304-3975(76)90059-1 |
| Reference:
|
[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. MR 0444516, 10.1137/0205049 |
| Reference:
|
[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, 10.1287/opre.12.3.450 |
| Reference:
|
[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. MR 0186497, 10.1287/opre.13.3.462 |
| Reference:
|
[10] S. L. Hakimi E. F. Schmeichel J. G. Pierce: Оn p-centers in networks.Transportation Sci. 12 (1978), 1 - 15. MR 0506674, 10.1287/trsc.12.1.1 |
| Reference:
|
[11] R. M. Karp: On the computational complexity of combinatorial problems.Networks 5 (1975), 45-68. Zbl 0324.05003, 10.1002/net.1975.5.1.45 |
| Reference:
|
[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 |
| Reference:
|
[13] E. Minieka: The centers and medians of a graph.Operations Res. 25 (1977), 641 - 650. Zbl 0383.90046, MR 0524906, 10.1287/opre.25.4.641 |
| Reference:
|
[14] S. C. Narula U. I. Оgbu H. M. Samuelsson: An algorithm for the p-median problem.Operations Res. 25 (1977), 709-713. MR 0446532, 10.1287/opre.25.4.709 |
| Reference:
|
[15] S. Sahni T. Gonzales: P-complete approximation problems.J. Assoc. Соmр. Mach. 23 (1976), 555-565. MR 0408313, 10.1145/321958.321975 |
| Reference:
|
[16] P. J. Slater: R-domination in graphs.J. Assoc. Сотр. Mach. 23 (1976), 445-450. Zbl 0349.05120, MR 0449602 |
| . |
