Multiobjective Genetic Algorithm for Minimum Weight Minimum Connected Dominating Set

摘要

Connected Dominating Set (CDS) is a connected subgraph of a graph G with the property that any given node in G either belongs to the CDS or is adjacent to one of the CDS nodes. Minimum Connected Dominating Sets (MCDS), where the CDS nodes are sought to be minimized, are of special interests in various fields like Computer networks, Biological networks, Social networks, etc., since they represent a set of minimal important nodes. Similarly, Minimum Weight Connected Dominating Sets (MWCDS), where the connected weights among the CDS nodes are sought to be minimized, is also of interest in many research application. This work is based on the hypothesis that a CDS with both the properties of minimum size and minimum weight optimized would enhance performance in many applications where CDS is used. Though there are a good number of approximate and heuristic algorithms for MCDS and MWMCDS, there is no work to the best of our knowledge, that optimizes the generated CDS with respect to both the size and weight. A Multiobjective Genetic Algorithm for Minimum Weight Minimum Connected Dominating Set (MOGA-MWMCDS) is proposed. Performance analysis based on a Wireless Sensor Network (WSN) scenario indicates the efficiency of the proposed MOGA-MWMCDS and supports the advantage of MWMCDS use.