Author name cluster

Pengjun Wan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

TCS Journal 2011 Journal Article

New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

Feng Zou
Yuexuan Wang
Xiao-Hua Xu
Xianyue Li
Hongwei Du
Pengjun Wan
Weili Wu

Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 + ε )-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 + ε )-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 + ε )-approximation algorithm for an MWCDS.

Details DOI

TCS Journal 2007 Journal Article

Algorithms for minimum m -connected k -tuple dominating set problem

Weiping Shang
Pengjun Wan
Frances Yao
Xiaodong Hu

In wireless sensor networks, a virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m -connected k -tuple dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. We propose three centralized algorithms with small approximation ratios for small m and improve the current best results for small k.

Details DOI