A local search algorithm based on non-dominated sorting for the minimum weight minimum connected dominating set problem

Optimization problems in practice often involve multiple conflicting objectives, which has motivated extensive research into multiobjective algorithms. In this work, the bi-objective minimum weight minimum connected dominating set problem, an NP-hard combinatorial problem that jointly minimizes the size of the connected dominating set and the sum of its associated edge weights, is addressed. A novel algorithm, called Non-dominated Sorting Local Search (NSLS), is proposed. The method begins with a semi-greedy construction of diverse initial solutions, followed by a randomized greedy local search procedure to improve them. To preserve diversity and approximate the Pareto front, the algorithm incorporates non-dominated sorting and crowding distance measures. Experimental results on standard benchmark instances show that NSLS achieves competitive performance and consistently outperforms several state-of-the-art algorithms across multiple evaluation metrics and statistical tests.