PTAS for Minimum k-Path Connected Vertex Cover in Growth-Bounded Graphs

详细信息    查看全文

• 作者：Yan Chu (24)
  Jianxi Fan (24)
  Wenjun Liu (24)
  Cheng-Kuan Lin (24)
  
• 关键词：PTAS ; k ; path connected vertex cover ; growth ; bounded graphs ; bounded degree ; wireless sensor networks
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8630
• 期：1
• 页码：114-126
• 全文大小：886 KB
• 参考文献：1. Bre?ar, B., Kardo?, F., Katreni?, J., Semani?in, G.: Minimum k-path vertex cover. Dis. Appl. Math.?159, 1189-195 (2011) CrossRef
  2. Liu, X., Lu, H., Wang, W., Wu, W.: PTAS for the minimum / k-path connected vertex cover problem in unit disk graphs. J. Global Opt.?56, 449-58 (2013) CrossRef
  3. Gollmann, D.: Protocol analysis for concrete environments. In: Moreno Díaz, R., Pichler, F., Quesada Arencibia, A. (eds.) EUROCAST 2005. LNCS, vol.?3643, pp. 365-72. Springer, Heidelberg (2005) CrossRef
  4. Menezes, A.J., Van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press (2010)
  5. Novotny, M.: Formal analysis of security protocols for wireless sensor networks. Tatra Mt. Math. Publ.?47, 81-7 (2010)
  6. Novotny, M.: Design and analysis of a generalized canvas protocol. In: Samarati, P., Tunstall, M., Posegga, J., Markantonakis, K., Sauveron, D. (eds.) WISTP 2010. LNCS, vol.?6033, pp. 106-21. Springer, Heidelberg (2010) CrossRef
  7. Vogt, H.: Integrity preservation for communication in sensor networks. Tech. Rep. 434, ETH Zurich, Institute for Pervasive Computing (2004)
  8. Vogt, H.: Exploring message authentication in sensor networks. In: 1st European Workshop Security Ad-Hoc Sensor Networks (2004)
  9. Vogt, H.: Increasing Attack Resiliency of Wireless Ad Hoc and Sensor Networks. In: 2nd International Workshop on Security in Distributed Computing Systems, pp. 179-184 (2005)
  10. Tu, J., Zhou, W.: A factor 2 approximation algorithm for the vertex cover P3 problem. Info Proc. Lett.?111, 683-86 (2011) CrossRef
  11. Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Local approximation schemes for ad hoc and sensor networks. In: DIALM-POMC Cologne, Germany, pp. 97-103 (2005)
  12. Nieberg, T., Hurink, J.: A PTAS for the minimum dominating set problem in unit disk graphs. In: Approximation and Online Algorithms, pp. 296-306 (2006)
  13. Gfeller, B., Vicari, E.: A Faster Distributed Approximation Scheme for the connected Dominating Set Problem for Growth-Bounded Graphs. In: 6th International Conference on Ad-Hoc, Mobile, and Wireless Networks, pp. 59-73 (2007)
  14. Gao, X., Wang, W., Zhang, Z., Zhu, S., Wu, W.: A PTAS for minimum / d-hop connected dominating set in growth-bounded graphs. Opt Lett?4, 321-33 (2010)
  15. Liu, Y., Fan, J., Wang, D., Du, H., Zhang, S., Lv, J.: Approximation Algorithms for Vertex Cover Problems in WSN Topology Design. Ad Hoc and Sensor Wireless Networks (accepted)
  16. Wang, Z., Wang, W., Kim, J.M., Thuraisingham, B., Wu, W.: PTAS for the minimum weighted dominating set in growth bounded graphs. J. Global Opt.?54, 641-48 (2012) CrossRef
  17. Nieberg, T., Hurink, J.L., Kern, W.: A robust ptas for maximum weight independent sets in unit disk graphs. In: Hromkovi?, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.?3353, pp. 214-21. Springer, Heidelberg (2004) CrossRef
  
• 作者单位：Yan Chu (24)
  Jianxi Fan (24)
  Wenjun Liu (24)
  Cheng-Kuan Lin (24)
  
  24. School of Computer Science and Technology, Soochow University, 215006, Suzhou, China
  
• ISSN：1611-3349

文摘

In the paper, we present a polynomial-time approximation scheme (PTAS) for the minimum k-path connected vertex cover (MkPCVC) problem , which can be used to solve security problems in wireless sensor networks (WSNs), under fixed k?2. In contrast to previously known approximation schemes for MkPCVC problem, our approach does not need location data of the vertices, and it can be applied to growth-bounded graphs. For any ε 1-0, the algorithm returns a (1+ε 1)-approximation MkPCVC. We have proved the correctness and performance of the algorithm and shown its runtime is r?em class="a-plus-plus">n O(f(r)), where f(r) is a polynomial function, r = O((1/ε)?ln(1/ε)) and ε is only dependent on k and ε 1.