  We present new greedy and beam search heuristic methods to find small-size
$k$-dominating sets in graphs. The methods are inspired by a new problem
formulation which explicitly highlights a certain structure of the problem. An
empirical evaluation of the new methods is done with respect to two existing
methods, using instances of graphs corresponding to street networks. The
k-domination problem with respect to this class of graphs can be used to model
real-world facility location problem scenarios. For the classic minimum
dominating set ($1$-domination) problem, all except one methods perform
similarly, which is due to their equivalence in this particular case. However,
for the k-domination problem with k>1, the new methods outperform the benchmark
methods, and the performance gain is more significant for larger values of k.
