Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks

摘要

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) ≤ α·m(u, v) where α 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 α ≥ 5, this problem has a polynomial-time approximation scheme, that is, for any ε > 0, there is a polynomial-time (1 + ε)-approximation.