Construction of Minimum Connected Dominating Set by using AJK Algorithm

Abstract

Dominating set, minimum dominating set and minimum connected dominating set is correct sequence need to study in any wireless network system. One must need to have MCDS for efficient and cost effective wireless network system. A graph G = (V; E), a dominating set D is a subset of V such that any vertex not in D is adjacent to at least one vertex in D. In a graph G = (V; E) a connected dominating set is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum connected dominating set is such a vertex subset with minimum cardinality. In this paper, we present a new method

i.e. AJK algorithm we can easily find a minimum connected dominating set. We can easily see that this algorithm gives a constant performance guarantee. The results show that, despite its simplicity, the proposed algorithm gives very good solutions.