Parameterized algorithms for power-efficient connected symmetric wireless sensor networks

Matthias Bentert, René van Bevern, André Nichterlein, Rolf Niedermeier

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

3 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииAlgorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers
ИздательSpringer-Verlag GmbH and Co. KG
Страницы26-40
Число страниц15
Том10718 LNCS
ISBN (печатное издание)9783319727509
DOI
СостояниеОпубликовано - 2017
Событие13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017 - Vienna, Австрия
Продолжительность: 4 сен 20178 сен 2017

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том10718 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017
СтранаАвстрия
ГородVienna
Период04.09.201708.09.2017

Fingerprint Подробные сведения о темах исследования «Parameterized algorithms for power-efficient connected symmetric wireless sensor networks». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать