An Efficient Centralized Algorithm for Connected Dominating Set on Wireless Networks | Zendy

Deqian Fu | Zendy; Lihua Han | Zendy; Li Liu | Zendy; Qian Gao | Zendy; Zhiquan Feng | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An Efficient Centralized Algorithm for Connected Dominating Set on Wireless Networks

Author(s) -

Deqian Fu,

Lihua Han,

Li Liu,

Qian Gao,

Zhiquan Feng

Publication year - 2015

Publication title -

procedia computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.334

H-Index - 76

ISSN - 1877-0509

DOI - 10.1016/j.procs.2015.07.190

Subject(s) - connected dominating set , computer science , construct (python library) , dominating set , redundancy (engineering) , computer network , set (abstract data type) , backbone network , graph , wireless network , algorithm , computation , wireless , distributed computing , theoretical computer science , telecommunications , vertex (graph theory) , programming language , operating system

In wireless network, backbone network plays an important role on forwarding data. Further, in order to reduce the delay and save energy, the minimum connected dominating set (MCDS) is an effective way to construct a backbone. However, it is NP-hard to construct the MCDS. In this paper, we propose an efficient centralized algorithm, redundancy connected dominating set (RCDS), to construct a relatively optimal connected dominating set with the economic computation cost of O(Δ2n) Specifically, the local strategy is employed to obtain the maximal independent set (MIS) firstly, and then a virtual backbone network is generated by adding the local joint intermediate nodes in the general graph

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research