The minimum connected dominating set (MCDS) problem is a very significant NP-hard combinatorial optimization problem, and it has been used in many fields such as wireless sensor networks and ad hoc networks. In this paper, we propose a novel multi-start local search algorithm (MSLS) to tackle the minimum connected dominating set problem. Firstly, we present the fitness mechanism to design the vertex score mechanism so that our algorithm can jump out of the local optimum. Secondly, we use the configuration checking (CC) mechanism to avoid the cycling problem. Then, we propose the vertex flipping mechanism to change the vertex state by combing the CC mechanism with the vertex score mechanism. Finally, we propose a multi-start local search framework based on these mechanisms. We compare the algorithm MSLS with other compared algorithms on extensive instances. The results of experiment show that MSLS is superior to other algorithms in solution quality and time efficiency on most instances.

The multi-objective minimum weighted vertex cover problem aims to minimize the sum of different single type weights simultaneously. In this paper, we focus on the bi-objective minimum weighted vertex cover and propose a multi-objective algorithm integrating iterated neighborhood search with decomposition technique to solve this problem. Initially, we adopt the decomposition method to divide the multi-objective problem into several scalar optimization sub-problems. Meanwhile, to find more possible optimal solutions, we design a mixed score function according to the problem feature, which is applied in initializing procedure and neighborhood search. During the neighborhood search, three operators ( $Add$ , $Delete$ , $Swap$ ) explore the search space effectively. We performed numerical experiments on many instances, and the results show the effectiveness of our new algorithm (combining decomposition and neighborhood search with mixed score) on several experimental metrics. We compared our experimental results with the classical multi-objective algorithm non-dominated sorting genetic algorithm II. It was obviously shown that our algorithm can provide much better results than the comparative algorithm considering the different metrics.

Given an undirected, connected and edge-weighted graph, the dominating tree problem consists of finding a tree with minimum total edge weight such that for each vertex is either in the tree or adjacent to a vertex in the tree. In this paper, we propose a hybrid framework combining genetic algorithm with iterated local search (GAITLS) for solving the dominating tree problem. The main components of our framework are as follows: (1) the score functions $Dscore$ and $Wscore$ applied in the initialization and local search phase; (2) the initialization procedure with restricted candidate list (RCL) by controlling the parameter to balance the greediness and randomness; (3) the iterated local search with three phases, which is used to intensify the individuals; (4) the mutation with high diversity proposed to perturb the population. The experimental results on the classical instances show that our method performs much better than the-state-of-art algorithms.