Group:Algorithms Group
Title: Distributed Construction of Connected Dominating Sets with Minimum Routing Cost
Speaker: Ding-Zhu Du University
Time: 2010-04-13 14:00-2010-04-13 15:00
Venue: FIT 1-222


In this paper, we will study a special Connected Dominating Set (CDS) problem. Between any two nodes in a network, there exists at least one shortest path, all of whose intermediate nodes should be included in the special CDS, named Minimum rOuting Cost CDS (MOC-CDS). Therefore, routing by MOC-CDS can guarantee that each routing path between any pair of nodes is also the shortest path in the network. We prove that the minimum MOC-CDS has no $( ho \ln \delta)$-approximation for $0 < ho < 1$ unless $NP \subseteq n^{O(\log\log n)}$ and present a distributed approximation algorithm with performance ratio $(1-\ln 2) + 2\ln \delta$ where $\delta$ is the maximum node degree of input graph. This is a joint work with Ling Ding, Xiaofeng Gao, Weili Wu, Wonjun Lee and Xu Zhu, to appear in ICDCS 2010.