\input zb-basic
\input zb-ioport
\iteman{io-port 06065016}
\itemau{Du, Hongwei; Ye, Qiang; Zhong, Jiaofei; Wang, Yuexuan; Lee, Wonjun; Park, Haesun}
\itemti{Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks.}
\itemso{Theor. Comput. Sci. 447, 38-43 (2012).}
\itemab
Summary: To reduce routing cost in wireless sensor networks, we study a problem of minimizing the size of connected dominating set $D$ under constraint that for any two nodes $u$ and $v$, $m_{D}(u,v) \le \alpha \cdot m(u,v)$ where $\alpha $ is a constant, $m_{D}(u,v)$ is the number of intermediate nodes on a shortest path connecting $u$ and $v$ through $D$ and $m(u,v)$ is the number of intermediate nodes in a shortest path between $u$ and $v$ in a given unit disk graph. We show that for $\alpha \ge 5$, this problem has a polynomial-time approximation scheme, that is, for any $\varepsilon >0$, there is a polynomial-time $(1+\varepsilon )$-approximation.
\itemrv{~}
\itemcc{}
\itemut{polynomial-time approximation; minimum connected dominating set; routing cost constraint; wireless sensor networks}
\itemli{doi:10.1016/j.tcs.2011.10.010}
\end