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.
关键词
元启发式算法/最小双连通支配集/变邻域搜索算法/禁忌算法/双连通图
Key words
A meta heuristic algorithm/minimum biconnected dominating set/variable neighborhood search algorithm/tabu search algorithm/biconnected graph
维普
万方数据