Much of the schemes for Multipoint Relay (MPR) selection in wireless ad hoc networks have been studied using the unit graph model, under the assumption that packets are always received without any error. As this model does not reflect the real scenario of transmissions, recent studies propose heuristics which enable selecting MPR under realistic assumptions. For this, they use redundancy to maximize the probability of delivery. But redundancy can increase the size of the MPR set, and therefore generating amounts of retransmissions and collisions, which can lead to degradation of the MPR protocol performance. Using reversible marking, a mechanism we presented in a previous study, we propose two heuristics which efficiently compute MPR. One of them resorts to redundancy and both compute a MPR set which size is at most log m greater than the optimum.