Distributed construction of connected dominating set in unit disk graphs

0534827 - ÚI 2021 eng J - Journal Article
Jallu, Ramesh Kumar - Prasad, P. R. - Das, G. K.
Distributed construction of connected dominating set in unit disk graphs.
Journal of Parallel and Distributed Computing. Roč. 104 (2017), s. 159-166. ISSN 0743-7315. E-ISSN 1096-0848
Keywords : wireless * algorithm * Unit disk graph * Approximation algorithm * Connected dominating set
Impact factor: 1.815, year: 2017

Let G = (V, E) be a unit disk graph corresponding to a given set P of n points in R-2. We propose a distributed approximation algorithm to find a minimum connected dominating set of G. The maintenance of the connected dominating set constructed is fully localized. Our algorithm produces a connected dominating set of size (104opt + 52), where opt is the size of a minimum connected dominating set. The time and message complexities of our algorithm are 0(Delta) and 0(n) respectively, where A and n are the maximum node degree and number of nodes in G respectively. Our distributed approximation algorithm outperforms existing algorithms in terms of its time and message complexities.
Permanent Link: http://hdl.handle.net/11104/0312992