Analysis of a Random Local Search Algorithm for Dominating Set

Hendrik Higl

Dominating Set is a well-known combinatorial optimization problem which finds application in computational biology or mobile communication. Because of its $\mathrm{NP}$-hardness, o…