TY - GEN
T1 - Approximating maximum disjoint coverage in wireless sensor networks
AU - Henna, Shagufta
AU - Erlebach, Thomas
PY - 2013
Y1 - 2013
N2 - Due to limited battery life and fault tolerance issues posed by Wireless Sensor Networks (WSNs), efficient methods which ensure reliable coverage are highly desirable. One solution is to use disjoint set covers to cover the targets. We formulate a problem called MDC which addresses the maximum coverage by using disjoint set covers S1 and S2. We prove that MDC is NP-complete and propose a √n-approximation algorithm for the MDC problem to cover n targets.
AB - Due to limited battery life and fault tolerance issues posed by Wireless Sensor Networks (WSNs), efficient methods which ensure reliable coverage are highly desirable. One solution is to use disjoint set covers to cover the targets. We formulate a problem called MDC which addresses the maximum coverage by using disjoint set covers S1 and S2. We prove that MDC is NP-complete and propose a √n-approximation algorithm for the MDC problem to cover n targets.
KW - Disjoint Coverage
KW - Disjoint Coverage NP-complete
KW - √n-approximation algorithm
UR - http://www.scopus.com/inward/record.url?scp=84884510608&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-39247-4_13
DO - 10.1007/978-3-642-39247-4_13
M3 - Conference contribution
AN - SCOPUS:84884510608
SN - 9783642392467
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 148
EP - 159
BT - Ad-hoc, Mobile, and Wireless Network - 12th International Conference, ADHOC-NOW 2013, Proceedings
T2 - 12th International Conference on Ad-hoc, Mobile and Wireless Networks, ADHOC-NOW 2013
Y2 - 8 July 2013 through 10 July 2013
ER -