Computer Science – Data Structures and Algorithms
Scientific paper
2011-07-25
Computer Science
Data Structures and Algorithms
Scientific paper
Given a graph with edge costs, the {\em power} of a node is themaximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider the following fundamental problem in wireless network design. Given a graph $G=(V,E)$ with edge costs and degree bounds $\{r(v):v \in V\}$, the {\sf Minimum-Power Edge-Multi-Cover} ({\sf MPEMC}) problem is to find a minimum-power subgraph $J$ of $G$ such that the degree of every node $v$ in $J$ is at least $r(v)$. We give two approximation algorithms for {\sf MPEMC}, with ratios $O(\log k)$ and $k+1/2$, where $k=\max_{v \in V} r(v)$ is the maximum degree bound. This improves the previous ratios $O(\log n)$ and $k+1$, and implies ratios $O(\log k)$ for the {\sf Minimum-Power $k$-Outconnected Subgraph} and $O(\log k \log \frac{n}{n-k})$ for the {\sf Minimum-Power $k$-Connected Subgraph} problems; the latter is the currently best known ratio for the min-cost version of the problem.
Cohen Nachshon
Nutov Zeev
No associations
LandOfFree
Approximating minimum-power edge-multicovers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximating minimum-power edge-multicovers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating minimum-power edge-multicovers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-572338