Samir Khuller (samir@cs.umd.edu), Sheng Yang (styang@cs.umd.edu)
University of Maryland, College Park
Sudipto Guha and Samir Khuller.
Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374–387, 1998.
1000+ citations
[BOOK] Protocols and architectures for wireless sensor networks
H Karl, A Willig - 2007 - books.google.com
On calculating connected dominating set for efficient routing in ad hoc wireless networks
J Wu, H Li - Proceedings of the 3rd international workshop on …, 1999 - dl.acm.org
Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks
I Stojmenovic, M Seddigh… - IEEE Transactions on …, 2002 - ieeexplore.ieee.org
A clustering scheme for hierarchical control in multi-hop wireless networks
S Banerjee, S Khuller - … Annual Joint Conference of the IEEE …, 2001 - ieeexplore.ieee.org
Connected sensor cover: self-organization of sensor networks networks for efficient query execution
H Gupta, Z Zhou, SR Das, Q Gu - IEEE/ACM Transactions on Networking …, 2006 - dl.acm.org
Minimum-energy broadcasting in static ad hoc wireless networks
PJ Wan, G Călinescu, XY Li, O Frieder - Wireless Networks, 2002 - Springer
An extended localized algorithm for connected dominating set formation in ad hoc wireless networks
F Dai, J Wu - IEEE transactions on parallel and distributed …, 2004 - ieeexplore.ieee.org
Given a graph $G$, find a CDS $S$, such that the size of $S$ is minimized
Choose a node that maximizes the number of newly covered nodes.
The result is not connected.
Choose a pair of nodes, i.e. a node and its neighbor, to maximize the number of newly covered nodes.
First globally select dominating set using greedy,
then connect them.
$O(\log(\Delta)) + O(1)$
Well.. anything better?
We first color all nodes white, and color it black when we select it. All dominated nodes are colored gray.
Every white node, or every connected component of black node, is considered as a piece.
Phase 1: globally select a node that maximizes the reduction of the number of pieces.
Phase 2: connect the pieces.
$\ln(\Delta) + O(1)$
C. Borgs, M. Brautbar, J. Chayes, S. Khanna, and B. Lucier
The power of local information in social networks. In Internet and Network Economics, pages 406–419. Springer, 2012
Do not know the whole graph.
Start from a random node to explore the graph.
Can only see nodes within some local neighborhood of the visited nodes.
When a new node is visited, you can see more nodes.
Visited nodes: $S$.
Visible nodes: $\bar{S} = \{u|\exists v\in S, \mathrm{s.\! t.}\ d(u,v) \leq k\}$.
The sub-graph induced by $\bar{S}$ is known.
The degree of nodes in $\bar{S}$ is visible.
Guha and Khuller's algorithm requires 2-hop local information.
Look among 1 hop neighborhood, and select a node $v$ that maximizes the number of newly covered nodes.
Then select one of the newly covered node uniformly at random.
Repeat the previous steps until all nodes are covered.
Still a $2\ln(\Delta) + O(1)$ approximation...
But
Requires less information.
Which implies...
Global * | $\ln(\Delta) + O(1)$ |
Local 2 hop * | $\color{red}{2}\ln(\Delta) + O(1)$ |
Local 1 hop ** | $\color{red}{2}\ln(\Delta) + O(1)$ |
Same framework.
Look among 2 hop neighborhood, and select 1 node $v$ that maximize a certain target function $f(v)$, until for all node $v$, $f(v)\leq 0$
NOTE: we do NOT maintain connectivity
$w_v$ is the number of new nodes that $v$ can cover.
$c_v$ is the number of components $v$ adjacent to.
Target function: $f(v) = 2w_v + c_v - 1$
Recall charging in Set Cover.
We charge when selecting a node, and split the charge magically among nodes.
Every node can be charged twice, the first time for being dominated, the second time for being connected.
For a node $v$ in OPT, bound the charge of all nodes that are covered by $v$ in OPT
Approximation ratio $\ln(2\Delta) + O(1)$.