## Matthias Bentert, René van Bevern, André Nichterlein, Rolf
Niedermeier, and Pavel V. Smirnov.
Parameterized algorithms for power-efficiently connecting sensor
networks: Theory and experiments.
2019.

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. On the negative side, we show that
o(logn)-approximating the difference d between the
optimal solution cost and a natural lower bound is
NP-hard and that, under the Exponential Time
Hypothesis, there are no exact algorithms running in
2^o(n) time or in f(d)⋅n^O(1) time for any computable
function f. On the positive side, we provide an
algorithm that reconnects O(logn) connected
components with minimum additional cost in
polynomial time. These algorithms are motivated by
application scenarios of monitoring areas or where
an existing sensor network may fall apart into
several connected components due to sensor
faults. In experiments, the algorithm solves
instances with four such connected components and
about 8 000 vertices in five minutes, outperforming
CPLEX with known ILP formulations for the problem.

[ bib |
source code |
http ]
Back

*This file was generated by
bibtex2html 1.99.*