  A dominating set of a graph $G=(V,E)$ is a subset of vertices $S\subseteq V$
such that every vertex $v\in V\setminus S$ has at least one neighbor in set
$S$. The corresponding optimization problem is known to be NP-hard. The best
known polynomial time approximation algorithm for the problem separates the
solution process in two stages applying first a fast greedy algorithm to obtain
an initial dominating set, and then it uses an iterative procedure to reduce
(purify) this dominating set. The purification stage turned out to be
practically efficient. Here we further strengthen the purification stage
presenting four new purification algorithms. All four purification procedures
outperform the earlier purification procedure. The algorithms were tested for
over 1300 benchmark problem instances. Compared to the known upper bounds, the
obtained solutions were about 7 times better. Remarkably, for the 500 benchmark
instances for which the optimum is known, the optimal solutions were obtained
for 46.33\% of the tested instances, whereas the average error for the
remaining instances was about 1.01.
