Recently I read this paper which was published in FOCS2007.

In section 4, just before Theorem 4.2, the author mentioned that the gadget construction of Minimum Dominating Set in UDG is similar to that of Maximal Independent Set. But it seemed a little bit difficult to find out the actual gadget construction for Minimal DS in UDG. Could you please give some more details about this construction?


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.