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 journalArticleResearchpeer-review

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

Fingerprint

Wireless sensor networks
apexes
topology
Topology
Polynomials
sensors
Approximation algorithms
polynomials
approximation
optimization
simulation

Keywords

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

Cite this

Liu, Yuanchao ; Fan, Jianxi ; Wang, Dajin ; Du, Hongwei ; Zhang, Shukui ; Lv, Jing. / Approximate algorithms for vertex cover problems in WSN topology design. In: Ad-Hoc and Sensor Wireless Networks. 2015 ; Vol. 28, No. 1-2. pp. 19-39.
@article{f67bfb6e0eba4b5387bfa064a1a7d656,
title = "Approximate algorithms for vertex cover problems in WSN topology design",
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.",
keywords = "Approximation algorithm, Bounded degree, Vertex cover, Wireless sensor networks",
author = "Yuanchao Liu and Jianxi Fan and Dajin Wang and Hongwei Du and Shukui Zhang and Jing Lv",
year = "2015",
month = "8",
day = "17",
language = "English",
volume = "28",
pages = "19--39",
journal = "Ad-Hoc and Sensor Wireless Networks",
issn = "1551-9899",
publisher = "Old City Publishing",
number = "1-2",

}

Liu, Y, Fan, J, Wang, D, Du, H, Zhang, S & Lv, J 2015, 'Approximate algorithms for vertex cover problems in WSN topology design', Ad-Hoc and Sensor Wireless Networks, vol. 28, no. 1-2, pp. 19-39.

Approximate algorithms for vertex cover problems in WSN topology design. / Liu, Yuanchao; Fan, Jianxi; Wang, Dajin; Du, Hongwei; Zhang, Shukui; Lv, Jing.

In: Ad-Hoc and Sensor Wireless Networks, Vol. 28, No. 1-2, 17.08.2015, p. 19-39.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Approximate algorithms for vertex cover problems in WSN topology design

AU - Liu, Yuanchao

AU - Fan, Jianxi

AU - Wang, Dajin

AU - Du, Hongwei

AU - Zhang, Shukui

AU - Lv, Jing

PY - 2015/8/17

Y1 - 2015/8/17

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - Bounded degree

KW - Vertex cover

KW - Wireless sensor networks

UR - http://www.scopus.com/inward/record.url?scp=84939236837&partnerID=8YFLogxK

M3 - Article

VL - 28

SP - 19

EP - 39

JO - Ad-Hoc and Sensor Wireless Networks

JF - Ad-Hoc and Sensor Wireless Networks

SN - 1551-9899

IS - 1-2

ER -