  Given a graph, the minimum dominating set (MinDS) problem is to identify a
smallest set $D$ of vertices such that every vertex not in $D$ is adjacent to
at least one vertex in $D$. The MinDS problem is a classic $\mathcal{NP}$-hard
problem and has been extensively studied because of its many disparate
applications in network analysis. To solve this problem efficiently, many
heuristic approaches have been proposed to obtain a good solution within an
acceptable time limit. However, existing MinDS heuristic algorithms are always
limited by various tie-breaking cases when selecting vertices, which slows down
the effectiveness of the algorithms. In this paper, we design an efficient
local search algorithm for the MinDS problem, named DmDS -- a dual-mode local
search framework that probabilistically chooses between two distinct
vertex-swapping schemes. We further address limitations of other algorithms by
introducing vertex selection criterion based on the frequency of vertices added
to solutions to address tie-breaking cases, and a new strategy to improve the
quality of the initial solution via a greedy-based strategy integrated with
perturbation. We evaluate DmDS against the state-of-the-art algorithms on seven
datasets, consisting of 346 instances (or families) with up to tens of millions
of vertices. Experimental results show that DmDS obtains the best performance
in accuracy for almost all instances and finds much better solutions than
state-of-the-art MinDS algorithms on a broad range of large real-world graphs.
