Abstract
In the Minimum k-Path Connected Vertex Cover Problem (MkPCVCP), we are given a connected graph G and an integer k ≥ 2, and are required to find a subset C of vertices with minimum cardinality such that each path with length k − 1 has a vertex in C, and moreover, the induced subgraph G[C] is connected. MkPCVCP is a generalization of the minimum connected vertex cover problem and has applications in many areas such as security communications in wireless sensor networks. MkPCVCP is proved to be NP-complete. In this paper, we give the first polynomial time approximation scheme (PTAS) for MkPCVCP in unit disk graphs, for every fixed k ≥ 2.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Brešar B., Kardoš F., Katrenič J., Semanišin G.: Minimum k-path vertex cover. Discrete Appl. Math. 159, 1189–1195 (2011)
Cheng X., Huang X., Li D., Wu W., Du D.: A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42, 202–208 (2003)
Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1978)
Gollmann, D.: Protocol Analysis for Concrete Environments, EUROCAST 2005. LNCS, vol. 3643, pp. 365–372. Springer, Heidelberg (2005)
Kratochvil, K.: Intersection graphs of noncrossing arc-connected sets in the plane. In: Proceedings of Symposium on Graph Drawing, GD’96. LNCS, vol. 1190, pp. 257–270 (1997)
Menezes A., van Oorshot P., Vanstone S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)
Novotný, M.: Formal Analysis of Security Protocols for Wireless Sensor Networks, accepted to Tatra Mountains Mathematical Publications (2010)
Novotný, M.: Design and analysis of a generalized canvas protocol. In: Proceedings of WISTP 2010. LNCS 6033, pp. 106–121. Springer (2010)
Tu T., Zhou W.: A factor 2 approximation algorithm for the vertex cover P 3 problem. Inf. Process. Lett. 111, 683–686 (2011)
Vogt, H.: Integrity preservation for communication in sensor networks. Technical report 434, Institute for Pervasive Computing, ETH Zürich (2004)
Vogt, H.: Exploring message authentication in sensor networks. In: Castelluccia, C., Hartenstein, H., Paar, C., Westhoff, D. (eds.) ESAS 2004. LNCS, vol. 3313, pp. 19–30. Springer, Heidelberg (2005)
Vogt, H.: Increasing attack resiliency of wireless ad hoc and sensor netmorks. In: Proceedings of the 2nd International Workshop on Security in Distributed Computing Systems (ICDCSW 2005), vol. 2, pp. 179–184. IEEE Computer Society, Washington (2005)
Wang L.S., Jiang T.: An approximation scheme for some steiner tree problems in the plane. Networks 28, 187–193 (1996)
Zhang Z., Gao X., Wu W.: PTAS for connected vertex cover in unit disk graphs. Theor. Comput. Sci. 410, 5398–5402 (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported in part by the Fundamental Research Funds for the Central Universities, the National Natural Science Foundation of China No. 11071191 and 11101329.
Rights and permissions
About this article
Cite this article
Liu, X., Lu, H., Wang, W. et al. PTAS for the minimum k-path connected vertex cover problem in unit disk graphs. J Glob Optim 56, 449–458 (2013). https://doi.org/10.1007/s10898-011-9831-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-011-9831-x