Network Lifetime and Power Assignment in ad hoc Wireless Networks
Lists
Only you see this
Abstract
Used for topology control in ad-hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity) The input consists of a directed complete weighted graph G=(V,c). The power of a vertex u in a directed spanning subgraph H is given by PH (u) = max uv ∈ E(H) c(uv). The power of H is given by $p(H) = \sum_{u \in v}p{\sc H}(u)$ , Power Assignment seeks to minimize p(H) while H satisfies the given connectivity constraint. We present asymptotically optimal O(log n)-approximation algorithms for three Power Assignment problems: Min-Power Strong Connectivity, Min-Power Symmetric Connectivity (the undirected graph having an edge uv iff H has both uv and vu must be connected) and Min-Power Broadcast (the input also has r ∈ V , and H must be a r-rooted outgoing spanning arborescence).
BibTeX
@inproceedings{calinescu2003network,
author = {Gruia Calinescu and Sanjiv Kapoor and Alexander Olshevsky and Alexander Zelikovsky},
title = {{Network Lifetime and Power Assignment in ad hoc Wireless Networks}},
booktitle = {ESA},
year = {2003},
url = {https://openreview.net/forum?id=C_oreRo1kL2},
}Loading related content...