A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph

Qinghai Liu, Zhao Zhang (), Yanmei Hong, Weili Wu and Ding-Zhu Du
Additional contact information
Qinghai Liu: Xinjiang University
Zhao Zhang: Xinjiang University
Yanmei Hong: Shanghai Univiersity
Weili Wu: University of Texas at Dallas
Ding-Zhu Du: University of Texas at Dallas

A chapter in Optimization, Simulation, and Control, 2013, pp 131-142 from Springer

Abstract: Abstract Considering the virtual backbone problem of wireless sensor networks with the shortest path constraint, the problem can be modeled as finding a minimum routing cost connected dominating set (MOC-CDS) in the graph. In this chapter, we study a variation of the MOC-CDS problem. Let k be a fixed positive integer. For any two vertices u, v of G and a vertex subset $$S \subseteq V (G)$$ , denote ℓ S (u, v) the length of the shortest (u, v)-path in G all whose intermediate vertices are in S and define $$g(u,v) = \left \{\begin{array}{@{}l@{\quad }l@{}} d(u,v) + 4, \quad &\mbox{ if }d(u,v) \leq k + 1; \\ (1 + \frac{4} {k})d(u,v) + 6,\quad &\mbox{ if }d(u,v) > k + 1. \end{array} \right.$$ The g-MOC-CDS problem asks for a subset S with the minimum cardinality such that S is a connected dominating set of G and $${\mathcal{l}}_{S}(u,v) \leq g(u,v)$$ for any pair of vertices (u, v) of G. Clearly, g-MOC-CDS can serve as a virtual backbone of the network such that the routing cost is not increased too much. In this chapter, we give a PTAS for the g-MOC-CDS problem on unit disk graphs.

Keywords: Connected dominating set; Unit disk graph; PTAS (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-1-4614-5131-0_9

Ordering information: This item can be ordered from
http://www.springer.com/9781461451310

DOI: 10.1007/978-1-4614-5131-0_9

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().