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)  = 5, this problem has a polynomial-time approximation scheme, that is, for any epsilon > 0, there is a polynomial-time (1 + epsilon)-approximation. (c) 2011 Elsevier B.V. All rights reserved.
polynomial-time approximation minimum connected dominating set routing cost constraint wireless sensor networks