  In this paper, we present a constructive heuristic algorithm for the
$2$-connected $m$-dominating set problem. It is based on a greedy heuristic in
which a 2-connected subgraph is iteratively extended with suitable open ears.
The growth procedure is an adaptation of the breadth-first-search which
efficiently manages to find open ears. Further, a heuristic function is defined
for selecting the best ear out of a list of candidates. The performance of the
basic approach is improved by adding a correction procedure which removes
unnecessary nodes from a generated solution. Finally, randomization is included
and the method is extended towards the GRASP metaheuristic. In our
computational experiments, we compare the performance of the proposed algorithm
to recently published results and show that the method is highly competitive
and especially suitable for dense graphs.

Discrete Mathematics