Journal of the Operational Research Society · 2017 · 13 citations · 26 references
Natural SciencesComputer ScienceMathematicsAlgorithmsOptimizationSet TheoryApproximation AlgorithmsMetaheuristic OptimizationDominating Set ApproximationDominating SetsLocal SearchLocal Search Optimization
The minimum capacitated dominating set problem, an extension of the classic minimum dominating set problem, is an important NP-hard combinatorial optimization problem with a wide range of applications. The aim of this paper is to design a novel local search algorithm to solve this problem. First, the vertex penalizing strategy is introduced to define the scoring method so that our algorithm could increase the diversity of the solutions. Accordingly, a two-mode dominated vertex selecting strategy is introduced to choose the dominated vertices by the added vertex to achieve more promising solutions. After that, an intensification scheme is proposed to make full use of the capacity of each vertex and to improve the solutions effectively. Based on these strategies, a novel local search framework, as we call local search based on vertex penalizing and two-mode dominated vertex selecting strategy (LS_PD), is presented. LS_PD is evaluated against several state-of-the-art algorithms on a large collection of benchmark instances. The experimental results show that in most benchmark instances, LS_PD performs better than its competitors in terms of both solution quality and computational efficiency.
26
On calculating connected dominating set for efficient routing in ad hoc wireless networks
Distributed clustering for ad hoc networks
Stefano Basagni · 2003 · 1K citations
Routing in ad-hoc networks using minimum connected dominating sets
Bevan Das, V. Bharghavan · 2002 · 771 citations
A literature survey on smart cities
Chuantao Yin, Zhang Xiong, Hui Chen et al. · Science China Information Sciences · 2015 · 718 citations