Variable Neighborhood Tabu Search for Solving Minimum Biconnected Dominating Set Problem
The minimum biconnected dominating set structure is used to construct a fault tolerant virtual back bone network of wireless sensor networks.A variable neighborhood tabu search algorithm(VNTS),is proposed to solve the minimum biconnected dominating set problem,which is a classical NP hard opti-mization problem.The algorithm transforms the original optimization problem into a series of decision problems,the k-biconnected dominating set problem,and uses two neighborhood structures to cover the solution space more efficiently.Meanwhile,a perturbation and a tabu mechanism are implemented to help the algorithm escape from the local optimal trap.The experiment on 38 public instances of biconnected graphs compares the proposed algorithms with the exact and heuristic algorithms in the literature.The re-sults show that the VNTS algorithm is competitive in solving the minimum biconnected dominating set problem.It obtains the optimal solutions of all the instances and outperforms other algorithms on dense graphs in terms of computational efficiency.
A meta heuristic algorithmminimum biconnected dominating setvariable neighborhood search algorithmtabu search algorithmbiconnected graph
万方数据
维普
