  We implement and test the performances of several approximation algorithms
for computing the minimum dominating set of a graph. These algorithms are the
standard greedy algorithm, the recent LP rounding algorithms and a hybrid
algorithm that we design by combining the greedy and LP rounding algorithms.
All algorithms perform better than anticipated in their theoretical analysis,
and have small performance ratios, measured as the size of output divided by
the LP objective lower-bound. However, each may have advantages over the
others. For instance, LP rounding algorithm normally outperforms the other
algorithms on sparse real-world graphs. On a graph with 400,000+ vertices, LP
rounding took less than 15 seconds of CPU time to generate a solution with
performance ratio 1.011, while the greedy and hybrid algorithms generated
solutions of performance ratio 1.12 in similar time. For synthetic graphs, the
hybrid algorithm normally outperforms the others, whereas for hypercubes and
k-Queens graphs, greedy outperforms the rest. Another advantage of the hybrid
algorithm is to solve very large problems where LP solvers crash, as
demonstrated on a real-world graph with 7.7 million+ vertices.
