Approximability results for the converse connected p-centre problemFootnote^†

† The abstract version of this paper was presented at the 38th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (38ACCMCC).

References

• S.K. Abu Nayeem and M. PAL, Genetic algorithm to solve the p-centre and p-radius problem on a network, International J. Comput. Math. 82 (2005), pp. 541–550. doi: 10.1080/00207160512331323380
   Web of Science ®Google Scholar
• J. Barilan and D. Peleg, Approximation algorithms for selecting network centers, Proceedings of the 2nd Workshop on Algorithms and Data Structures, Canada, Dehne/Sack/Santoro, Lecture Notes in Computer Science Vol. 519, 1991, pp. 343–354.
   Google Scholar
• J. Barilan, G. Kortsarz, and D. Peleg, How to allocate network centers, J. Algorithms 15 (1993), pp. 385–415. doi: 10.1006/jagm.1993.1047
   Web of Science ®Google Scholar
• C. Berge, Theory and Graphs and its Applications, Methuen, London, 1962.
   Google Scholar
• K. Bharath-Kumar and J. Jaffe, Routing to multiple destinations in computer networks, IEEE Trans. Commun. 31 (1983), pp. 343–351. doi: 10.1109/TCOM.1983.1095818
   Web of Science ®Google Scholar
• A. Chaudhury, P. Basuchowdhuri, and S. Majumder, Spread of information in a social network using influential nodes, Advances in Knowledge Discovery and Data Mining, Malaysia, Tan/Chawla/Ho/Bailey, Lecture Notes in Computer Science Vol. 7302, 2012, pp. 121–132.
   Google Scholar
• C.H. Chow, On multicast path finding algorithms, Proceedings of the IEEE INFOCOM, Bal Harbour, FL, USA, 1991, pp. 1274–1283.
   Google Scholar
• E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), pp. 247–261. doi: 10.1002/net.3230070305
   Google Scholar
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithm, 3rd ed., MIT Press, Cambridge, 2009.
   Google Scholar
• M.S. Daskin, Network and Discrete Location: Models Algorithms and Applications, Wiley, New York, 1995.
   Google Scholar
• M.S. Daskin, What you should know about location modeling, Naval Res. Logist. 55 (2008), pp. 283–294. doi: 10.1002/nav.20284
   Web of Science ®Google Scholar
• R.W. Floyd, Algorithm 97: shortest path, Commun. ACM 5 (1962), pp. 345. doi: 10.1145/367766.368168
   Web of Science ®Google Scholar
• M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco, CA, 1979.
   Google Scholar
• A. Goel, K.G. Ramakrishnan, D. Kataria, and D. Logothetis, Efficient computation of delay-sensitive routes from one source to all destinations, Proceedings of the IEEE INFOCOM, Anchorage, AK, USA, 2001, pp. 854–858.
   Google Scholar
• T.F. Gonzalez, Clustering to minimize the maximum intercluster distance, Theoret. Comput. Sci. 38 (1985), pp. 293–306. doi: 10.1016/0304-3975(85)90224-5
   Web of Science ®Google Scholar
• S. Guha and S. Khuller, Approximation algorithms for connected dominating sets, Algorithmica 20 (1998), pp. 374–387. doi: 10.1007/PL00009201
   Web of Science ®Google Scholar
• S.L. Hakimi, Optimal distribution of switching centers in a communication network and some related graph theoretic problems, Oper. Res. 13 (1965), pp. 462–475. doi: 10.1287/opre.13.3.462
   Web of Science ®Google Scholar
• D.S. Hochbaum, Various notions of approximations: Good, better, best, and more, in Approximation Algorithms for NP-hard Problems, D.S. Hochbaum, ed., PWS Publishing Company, Boston, MA, 1997, pp. 346–398.
   Google Scholar
• D.S. Hochbaum and A. Pathria, Generalized p-center problems: complexity results and approximation algorithms, Eur. J. Oper. Res. 100 (1997), pp. 594–607. doi: 10.1016/S0377-2217(96)00076-8
   Web of Science ®Google Scholar
• D.S. Hochbaum and D.B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, J. ACM 33 (1986), pp. 533–550. doi: 10.1145/5925.5933
   Web of Science ®Google Scholar
• W.-L. Hsu and G.L. Nemhauser, Easy and hard bottleneck location problems, Discrete Appl. Math. 1 (1979), pp. 209–215. doi: 10.1016/0166-218X(79)90044-1
   Web of Science ®Google Scholar
• D.B. Johnson, Efficient algorithms for shortest paths in sparse networks, J. ACM 24 (1977), pp. 1–13. doi: 10.1145/321992.321993
   Web of Science ®Google Scholar
• V. Kann, On the Approximability of NP-complete Optimization Problems, Ph.D. thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992.
   Google Scholar
• O. Kariv and S.L. Hakimi, An algorithmic approach to network location problems I: The p-centers, SIAM J. Appl. Math. 37 (1979), pp. 514–538.
   Google Scholar
• V.P. Kompella, J.C. Pasquale, and G.C. Polyzos, Multicast routing for multimedia communication, IEEE/ACM Trans. Netw. 1 (1993), pp. 286–292. doi: 10.1109/90.234851
   Web of Science ®Google Scholar
• M.V. Marathe, R. Ravi, R. Sundaram, S.S. Ravi, D.J. Rosenkrantz, and H.B. Hunt III, Bicriteria network design problems, J. Algorithms 28 (1998), pp. 142–171. doi: 10.1006/jagm.1998.0930
   Web of Science ®Google Scholar
• J. Mihelic and B. Robic, Facility location and covering problems, Proceedings of the 7th International Multiconference Information Society, Vol. D–Theoretical Computer Science, Ljubljana, Slovenia, 2004.
   Google Scholar
• O. Ore, Theory of Graphs, American Mathematical Society Colloquium Publications, Providence, Rhode Island, 1962.
   Google Scholar
• C.H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. Syst. Sci. 43 (1991), pp. 425–440. doi: 10.1016/0022-0000(91)90023-X
   Web of Science ®Google Scholar
• J. Plesnik, A heuristic for the p-center problems in graphs, Discrete Appl. Math. 17 (1987), pp. 263–268. doi: 10.1016/0166-218X(87)90029-1
   Web of Science ®Google Scholar
• W. Ren and Q. Zhao, A note on Algorithms for connected set cover problem and fault-tolerant connected set cover problem, Theoret. Comput. Sci. 412 (2011), pp. 6451–6454. doi: 10.1016/j.tcs.2011.07.008
   Web of Science ®Google Scholar
• C.S. ReVelle and H.A. Eiselt, Location analysis: a synthesis and survey, European Journal of Operational Research 165 (2005), pp. 1–19. doi: 10.1016/j.ejor.2003.11.032
   Web of Science ®Google Scholar
• C.S. ReVelle, H.A. Eiselt, and M.S. Daskin, A bibliography for some fundamental problem categories in discrete location science, Eur. J. Oper. Res. 184 (2008), pp. 817–848. doi: 10.1016/j.ejor.2006.12.044
   Web of Science ®Google Scholar
• T. Shuai and X.-D. Hu, Connected set cover problem and its applications, in Proceedings of the Algorithmic Aspects in Information and Management, China, S.-W. Cheng and C.K. Poon, eds., Lecture Notes in Computer Science, Vol. 4041, 2006, pp. 243–254.
   Google Scholar
• T. Takaoka, Effcient algorithms for the 2-center problems, Proceedings of the 10th International Conference on Computational Science and Applications, Taniar/Gervasi/Murgante/Pardede/Apduhan, Lecture Notes in Computer Science, Vol. 6017, Springer, Fukuoka, 2010, pp. 519–532.
   Google Scholar
• A. Tamir, Improved complexity bounds for center location problems on networks by using dynamic data structures, SIAM J. Discrete Math. 1 (1988), pp. 377–396. doi: 10.1137/0401038
   Google Scholar
• B.C. Tansel, R.L. Francis, and T.J. Lowe, Location on networks: a survey. Part I: the p-center and p-median problems, Manage. Sci. 29 (1983), pp. 482–497. doi: 10.1287/mnsc.29.4.482
   Web of Science ®Google Scholar
• V.V. Vazirani, Approximation Algorithms, Springer-Verlag, Berlin, 2001.
   Google Scholar
• D.B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, Upper Saddle River, NJ, 2001.
   Google Scholar
• W.C.-K. Yen, The connected p-center problem on block graphs with forbidden vertices, Theoret. Comput. Sci. 426 (2012), pp. 13–24. doi: 10.1016/j.tcs.2011.12.013
   Web of Science ®Google Scholar
• W.C.-K. Yen and C.-T. Chen, The p-center problem with connectivity constraint, Appl. Math. Sci. 1 (2007), pp. 1311–1324.
   Google Scholar
• W. Zhang, W. Wu, W. Lee, and D.-Z. Du, Complexity and approximation of the connected set-cover problem, J. Global Optim. 53 (2012), pp. 563–572. doi: 10.1007/s10898-011-9726-x
   Web of Science ®Google Scholar