## M. Bentert, R. van Bevern, A. Nichterlein, and R. Niedermeier.
Parameterized algorithms for power-efficient connected symmetric
wireless sensor networks.
2017.

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(logn)
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(logn). 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 there are presumably no exact
algorithms running in 2o(n) time or in f(d)⋅nO(1)
time for any computable function f.

[ bib |
http ]
Back

*This file was generated by
bibtex2html 1.98.*