Imperialist Competitive Algorithm for Connected Dominating Set in Unit Disk Graphs

Since it is NP-complete to solve the connected dominating set problem (CDS) even approximatively, meta-heuristic algorithms are proper to solve it. In this paper, we present an imperialist competitive algorithm (ICA) for CDS. ICA is an evolutionary optimization Algorithm motivated by the socio-political process of imperialistic competition and has proven its superior performance, such as faster convergence and better global minimum achievement. We compare the results produced by other algorithms with our algorithm, which proved the effectiveness of the ICA.

Keywords:

Data Combinatorial Optimization , Evolutionary Algorithm , Minimum Independent Set , Imperialist Competitive Algorithm