Summary
The 2018 International Symposium on Information Theory and Its Applications　(ISITA2018)
2018
Session Number:Mo-PM-2-3
Session:
Number:Mo-PM-2-3.4
Analysis on Probabilistic Construction of Connected Dominating Sets over Regular Graph Ensembles
Takafumi Nakano, Tadashi Wadayama,
pp.247-251
Publication Date:2018/10/18
Online ISSN:2188-5079
DOI:10.34385/proc.55.Mo-PM-2-3.4
PDF download
Summary:
In this paper, we propose a simple probabilistic construction of connected dominating sets (CDS) that is useful for virtual backbones of wireless ad-hoc networks. In the construction, each node in a network has a random bit and the node joins the virtual backbone if and only if the random bit is one. Our main contribution is to derive the exact formula of the expected success probability of the probabilistic CDS construction over regular graph ensembles. The derivation of the formula is based on a counting argument for a special class of labeled simple graphs with socket nodes. The ensemble average indicates the typical performance of the proposed probabilistic CDS construction and the expected values can be efficiently evaluated in polynomial time.