Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Parameterized algorithms for power-efficient connected symmetric wireless sensor networks. / Bentert, Matthias; van Bevern, René; Nichterlein, André et al.
Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers. Vol. 10718 LNCS Springer-Verlag GmbH and Co. KG, 2017. p. 26-40 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10718 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Parameterized algorithms for power-efficient connected symmetric wireless sensor networks
AU - Bentert, Matthias
AU - van Bevern, René
AU - Nichterlein, André
AU - Niedermeier, Rolf
N1 - Publisher Copyright: © Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless sensor communication network. Given an edge-weighted n-vertex graph, find a connected spanning subgraph of minimum cost, where the cost is determined by letting each vertex pay the most expensive edge incident to it in the subgraph. We provide an algorithm that works in polynomial time if one can find a set of obligatory edges that yield a spanning subgraph with O(log n) connected components. We also provide a linear-time algorithm that reduces any input graph that consists of a tree together with g additional edges to an equivalent graph with O(g) vertices. Based on this, we obtain a polynomial-time algorithm for g∈ O(log n). On the negative side, we show that o(log n)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard and that there are presumably no exact algorithms running in 2°(n) time or in f(d) · nO(1) time for any computable function f.
AB - We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless sensor communication network. Given an edge-weighted n-vertex graph, find a connected spanning subgraph of minimum cost, where the cost is determined by letting each vertex pay the most expensive edge incident to it in the subgraph. We provide an algorithm that works in polynomial time if one can find a set of obligatory edges that yield a spanning subgraph with O(log n) connected components. We also provide a linear-time algorithm that reduces any input graph that consists of a tree together with g additional edges to an equivalent graph with O(g) vertices. Based on this, we obtain a polynomial-time algorithm for g∈ O(log n). On the negative side, we show that o(log n)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard and that there are presumably no exact algorithms running in 2°(n) time or in f(d) · nO(1) time for any computable function f.
KW - Approximation hardness
KW - Color coding
KW - Data reduction
KW - Monitoring areas and backbones
KW - Parameterization above lower bounds
KW - Parameterized complexity
KW - Spanning trees
UR - http://www.scopus.com/inward/record.url?scp=85040097095&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-72751-6_3
DO - 10.1007/978-3-319-72751-6_3
M3 - Conference contribution
AN - SCOPUS:85040097095
SN - 9783319727509
VL - 10718 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 26
EP - 40
BT - Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers
PB - Springer-Verlag GmbH and Co. KG
T2 - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017
Y2 - 4 September 2017 through 8 September 2017
ER -
ID: 9088179