Approximate algorithms for vertex cover problems in WSN topology design

Yuanchao Liu, Jianxi Fan, Dajin Wang, Hongwei Du, Shukui Zhang, Jing Lv

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

The Vertex Cover (VC) problem is a classical optimization problem that can be applied in topology design in Wireless Sensor Networks (WSNs). In this paper, we first propose two polynomial time approximation schemes (PTASs) for the Minimum Vertex Cover (MVC) problem and the Minimum Weighted Vertex Cover (MWVC) problem in growth-bounded graphs. We then propose an approximation algorithm, with a performance guarantee of (1 +2ε/(1 -ε)) for sufficiently small ε>0, for the Minimum Connected Vertex Cover (MCVC) problem. In contrast to previously proposed schemes for VC problems, our approach does not assume geometric representation of vertices in growth-bounded graphs. We also prove that the running times of the proposed algorithms are bounded by a polynomial in terms of the graph size and the input ε. We evaluate the performance of our algorithms through simulation.

Original languageEnglish
Pages (from-to)19-39
Number of pages21
JournalAd-Hoc and Sensor Wireless Networks
Volume28
Issue number1-2
StatePublished - 17 Aug 2015

Keywords

  • Approximation algorithm
  • Bounded degree
  • Vertex cover
  • Wireless sensor networks

Fingerprint Dive into the research topics of 'Approximate algorithms for vertex cover problems in WSN topology design'. Together they form a unique fingerprint.

  • Cite this