<p>Recently I read <a href="http://www.cs.bme.hu/~dmarx/papers/marx-focs2007-ptas.pdf" rel="nofollow">this paper</a> which was published in FOCS2007. </p>

<p>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?</p>

CC BY-SA 3.0
2016-02-12T12:55:10.763Z
you can find in his slides http://www.cs.bme.hu/~dmarx/papers/marx-icerm2014-complexity-slides.pdf and http://www.cs.bme.hu/~dmarx/papers/krakow2015-slides7.pdf
Yixin Cao
CC BY-SA 3.0
2016-02-13T21:32:31.047Z
@Yixin Cao Sorry but I cannot find the reduction in both slides. Could you please specify the page number? Thanks in advance!
Ruosong Wang
<approximation-algorithms><reductions>
L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph
Ruosong Wang
# L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph

(Asked by: username_0 on 2016-02-11)

Recently I read [this paper](http://www.cs.bme.hu/~dmarx/papers/marx-focs2007-ptas.pdf) 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?

**Tags:** approximation-algorithms, reductions
> **Comments:**
> **username_1**: you can find in his slides http://www.cs.bme.hu/~dmarx/papers/marx-icerm2014-complexity-slides.pdf and http://www.cs.bme.hu/~dmarx/papers/krakow2015-slides7.pdf  
> **username_0**: @Yixin Cao Sorry but I cannot find the reduction in both slides. Could you please specify the page number? Thanks in advance!  

---

## 0 answers

