### 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 language | English |
---|---|

Pages (from-to) | 19-39 |

Number of pages | 21 |

Journal | Ad-Hoc and Sensor Wireless Networks |

Volume | 28 |

Issue number | 1-2 |

State | Published - 17 Aug 2015 |

### Fingerprint

### Keywords

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

### Cite this

*Ad-Hoc and Sensor Wireless Networks*,

*28*(1-2), 19-39.

}

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

Research output: Contribution to journal › Article › Research › peer-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 -