I have a synchronic ring network with $n$ (i.e. the nodes are connected in a ring), and I need a good approximation (factor of 3/2 of the optimal value) for the minimal dominating set.

I also need this to be done in $O(\log^*n)$, where $n$ is the number of nodes in the network.

I’m using the LOCAL distributed computational model.

  • $\begingroup$ What is the computation model? And also, what dod you try, where did you get stuck? $\endgroup$
    – nir shahar
    Jun 13 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.