On parallelizing a greedy heuristic for finding small dominant sets

We analyse a greedy heuristic for finding small dominating sets in graphs: bounds on the size of the dominating set so produced had previously been derived in terms of the size of a smallest dominating set and the number of vertices and edges in the graph, respectively, We show that computing the resulting small dominating set isP-hard and so cannot be done efficiently in parallel (in the context of the PRAM model of parallel computation). We also consider a related non-deterministic greedy heuristic.