Number of the records: 1
Distributed construction of connected dominating set in unit disk graphs
- 1.
SYSNO ASEP 0534827 Document Type J - Journal Article R&D Document Type The record was not marked in the RIV Subsidiary J Článek ve WOS Title Distributed construction of connected dominating set in unit disk graphs Author(s) Jallu, Ramesh Kumar (UIVT-O) RID, ORCID, SAI
Prasad, P. R. (US)
Das, G. K. (IN)Number of authors 3 Source Title Journal of Parallel and Distributed Computing. - : Elsevier - ISSN 0743-7315
Roč. 104 (2017), s. 159-166Language eng - English Keywords wireless ; algorithm ; Unit disk graph ; Approximation algorithm ; Connected dominating set UT WOS 000398763100013 EID SCOPUS 85012146189 DOI 10.1016/j.jpdc.2017.01.023 Annotation 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. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2021
Number of the records: 1