Parameterized algorithms for power-efficient connected symmetric wireless sensor networks

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationAlgorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers
PublisherSpringer-Verlag GmbH and Co. KG
Pages26-40
Number of pages15
Volume10718 LNCS
ISBN (Print)9783319727509
DOIs
Publication statusPublished - 2017
Event13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017 - Vienna, Austria
Duration: 4 Sep 20178 Sep 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10718 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017
CountryAustria
CityVienna
Period04.09.201708.09.2017

Keywords

  • Approximation hardness
  • Color coding
  • Data reduction
  • Monitoring areas and backbones
  • Parameterization above lower bounds
  • Parameterized complexity
  • Spanning trees

Fingerprint

Dive into the research topics of 'Parameterized algorithms for power-efficient connected symmetric wireless sensor networks'. Together they form a unique fingerprint.

Cite this