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 -