Local Search for Minimum Weight Dominating Set with Two-Level
  Configuration Checking and Frequency Based Scoring Function
  The Minimum Weight Dominating Set (MWDS) problem is an important
generalization of the Minimum Dominating Set (MDS) problem with extensive
applications. This paper proposes a new local search algorithm for the MWDS
problem, which is based on two new ideas. The first idea is a heuristic called
two-level configuration checking (CC2), which is a new variant of a recent
powerful configuration checking strategy (CC) for effectively avoiding the
recent search paths. The second idea is a novel scoring function based on the
frequency of being uncovered of vertices. Our algorithm is called CC2FS,
according to the names of the two ideas. The experimental results show that,
CC2FS performs much better than some state-of-the-art algorithms in terms of
solution quality on a broad range of MWDS benchmarks.
