Mechanism (biology)

Quantum mechanics

Algorithm

Connected dominating set

Theoretical computer science

Vertex (graph theory)

Local search (optimization)

Wireless ad hoc network

Telecommunications

Set (abstract data type)

Computer science

Physics

Minimum spanning tree

Graph

Dominating set

Programming language

Wireless

Feedback vertex set

Mathematics

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.

Multi-Start Local Search Algorithm for the Minimum Connected Dominating Set Problems