TY - JOUR
T1 - On minimum power connectivity problems
AU - Lando, Yuval
AU - Nutov, Zeev
N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.
PY - 2010/6
Y1 - 2010/6
N2 - Given a (directed or undirected) graph with edge costs, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Motivated by applications for wireless networks, we present polynomial and improved approximation algorithms, as well as inapproximability results, for some classic network design problems under the power minimization criteria. Our main result is for the problem of finding a min-power subgraph that contains k internally-disjoint vs-paths from every node v to a given node s: we give a polynomial algorithm for directed graphs and a logarithmic approximation algorithm for undirected graphs. In contrast, we will show that the corresponding edge-connectivity problems are unlikely to admit even a polylogarithmic approximation.
AB - Given a (directed or undirected) graph with edge costs, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Motivated by applications for wireless networks, we present polynomial and improved approximation algorithms, as well as inapproximability results, for some classic network design problems under the power minimization criteria. Our main result is for the problem of finding a min-power subgraph that contains k internally-disjoint vs-paths from every node v to a given node s: we give a polynomial algorithm for directed graphs and a logarithmic approximation algorithm for undirected graphs. In contrast, we will show that the corresponding edge-connectivity problems are unlikely to admit even a polylogarithmic approximation.
KW - Approximation algorithms
KW - Connectivity
KW - Power assignment
KW - Wireless networks
UR - http://www.scopus.com/inward/record.url?scp=77649236353&partnerID=8YFLogxK
U2 - 10.1016/j.jda.2009.03.002
DO - 10.1016/j.jda.2009.03.002
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:77649236353
SN - 1570-8667
VL - 8
SP - 164
EP - 173
JO - Journal of Discrete Algorithms
JF - Journal of Discrete Algorithms
IS - 2
ER -