On minimum m-connected k-dominating set problem in unit disc graphs

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

37 Scopus Citations
View graph of relations

Author(s)

  • Weiping Shang
  • Frances Yao
  • Pengjun Wan
  • Xiaodong Hu

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)99-106
Journal / PublicationJournal of Combinatorial Optimization
Volume16
Issue number2
Publication statusPublished - Aug 2008

Abstract

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a S ⊆ V of minimal size such that every vertex in V\S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m ≤ 2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. © 2007 Springer Science+Business Media, LLC.

Research Area(s)

  • Approximation algorithm, k-dominating set, m-connectivity, Unit disc graph, Wireless sensor networks

Citation Format(s)

On minimum m-connected k-dominating set problem in unit disc graphs. / Shang, Weiping; Yao, Frances; Wan, Pengjun; Hu, Xiaodong.

In: Journal of Combinatorial Optimization, Vol. 16, No. 2, 08.2008, p. 99-106.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review