Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments

Matthias Bentert, Rene van Bevern, Andre Nichterlein, Rolf Niedermeier, Pavel V. Smirnov

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

We study a problem of energy-efficiently connecting a symmetric wireless communication network: given an n-vertex graph with edge weights, find a connected spanning subgraph of minimum cost, where the cost is determined by each vertex paying the heaviest edge incident to it in the subgraph. The problem is known to be NP-hard. Strengthening this hardness result, we show that even o(log n)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard. Moreover, we show that under the exponential time hypothesis, there are no exact algorithms running in 2o(n) time or in f(d)·nO(1) time for any computable function f. We also show that the special case of connecting c network components with minimum additional cost generally cannot be polynomial-time reduced to instances of size cO(1) unless the polynomial-time hierarchy collapses. On the positive side, we provide an algorithm that reconnects O(log n)-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 because of sensor faults. In experiments, the algorithm outperforms CPLEX with known integer linear programming (ILP) formulations when n is sufficiently large compared with c.

Язык оригиналаанглийский
Страницы (с-по)55-75
Число страниц21
ЖурналInforms journal on computing
Том34
Номер выпуска1
DOI
СостояниеОпубликовано - янв. 2022

Предметные области OECD FOS+WOS

  • 1.02.EV ИНФОРМАТИКА, МЕЖДИСЦИПЛИНАРНЫЕ ПРИМЕНЕНИЯ
  • 5.02.PE ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И НАУКА УПРАВЛЕНИЯ

Fingerprint

Подробные сведения о темах исследования «Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать