Routing-efficient CDS construction in Disk-Containment Graphs

Zaixin Lu, Lidong Wu, Panos M. Pardalos, Eugene Maslov, Wonjun Lee, Ding Zhu Du

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


In wireless networks, Connected Dominating Sets (CDSs) are widely used as virtual backbones for communications. On one hand, reducing the backbone size will reduce the maintenance overhead. So how to minimize the CDS size is a critical issue. On the other hand, when evaluating the performance of a wireless network, the hop distance between two communication nodes, which reflect the energy consumption and response delay, is of great importance. Hence how to minimize the routing cost is also a key problem for constructing the network virtual backbone. In this paper, we study the problem of constructing applicable CDS in wireless networks in terms of size and routing cost. We formulate a wireless network as a Disk-Containment Graph (DCG), which is a generalization of the Unit-Disk Graph (UDG), and we develop an efficient algorithm to construct CDS in such kind of graphs. The algorithm contains two parts and is flexible to balance the performance between the two metrics. We also analyze the algorithm theoretically. It is shown that our algorithm has provable performance in minimizing the CDS size and reducing the communication distance for routing.

Original languageEnglish
Pages (from-to)425-434
Number of pages10
JournalOptimization Letters
Issue number2
Publication statusPublished - 2014 Feb


  • Approximation algorithm
  • CDS
  • Routing efficiency
  • Wireless network

ASJC Scopus subject areas

  • Control and Optimization


Dive into the research topics of 'Routing-efficient CDS construction in Disk-Containment Graphs'. Together they form a unique fingerprint.

Cite this