Deterministic distributed construction of T-dominating sets in time T

Finally, when T∈o(log∗n), the above lower bound implies that, for any constant x<1, it is impossible to construct a T-dominating set of size smaller than xn, even on rings. On the positive side, we provide an algorithm that constructs a T-dominating set of size n−Θ(T) on all graphs.