Standard

Parameterized algorithms for power-efficient connected symmetric wireless sensor networks. / Bentert, Matthias; van Bevern, René; Nichterlein, André и др.

Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers. Том 10718 LNCS Springer-Verlag GmbH and Co. KG, 2017. стр. 26-40 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10718 LNCS).

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

Harvard

Bentert, M, van Bevern, R, Nichterlein, A & Niedermeier, R 2017, Parameterized algorithms for power-efficient connected symmetric wireless sensor networks. в Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers. Том. 10718 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 10718 LNCS, Springer-Verlag GmbH and Co. KG, стр. 26-40, 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Vienna, Австрия, 04.09.2017. https://doi.org/10.1007/978-3-319-72751-6_3

APA

Bentert, M., van Bevern, R., Nichterlein, A., & Niedermeier, R. (2017). Parameterized algorithms for power-efficient connected symmetric wireless sensor networks. в Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers (Том 10718 LNCS, стр. 26-40). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10718 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-72751-6_3

Vancouver

Bentert M, van Bevern R, Nichterlein A, Niedermeier R. Parameterized algorithms for power-efficient connected symmetric wireless sensor networks. в Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers. Том 10718 LNCS. Springer-Verlag GmbH and Co. KG. 2017. стр. 26-40. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-72751-6_3

Author

Bentert, Matthias ; van Bevern, René ; Nichterlein, André и др. / Parameterized algorithms for power-efficient connected symmetric wireless sensor networks. Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers. Том 10718 LNCS Springer-Verlag GmbH and Co. KG, 2017. стр. 26-40 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{7a95204cc7274157b14c27563b1797cd,
title = "Parameterized algorithms for power-efficient connected symmetric wireless sensor networks",
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.",
keywords = "Approximation hardness, Color coding, Data reduction, Monitoring areas and backbones, Parameterization above lower bounds, Parameterized complexity, Spanning trees",
author = "Matthias Bentert and {van Bevern}, Ren{\'e} and Andr{\'e} Nichterlein and Rolf Niedermeier",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017 ; Conference date: 04-09-2017 Through 08-09-2017",
year = "2017",
doi = "10.1007/978-3-319-72751-6_3",
language = "English",
isbn = "9783319727509",
volume = "10718 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "26--40",
booktitle = "Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers",
address = "Germany",

}

RIS

TY - GEN

T1 - Parameterized algorithms for power-efficient connected symmetric wireless sensor networks

AU - Bentert, Matthias

AU - van Bevern, René

AU - Nichterlein, André

AU - Niedermeier, Rolf

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Approximation hardness

KW - Color coding

KW - Data reduction

KW - Monitoring areas and backbones

KW - Parameterization above lower bounds

KW - Parameterized complexity

KW - Spanning trees

UR - http://www.scopus.com/inward/record.url?scp=85040097095&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-72751-6_3

DO - 10.1007/978-3-319-72751-6_3

M3 - Conference contribution

AN - SCOPUS:85040097095

SN - 9783319727509

VL - 10718 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 26

EP - 40

BT - Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers

PB - Springer-Verlag GmbH and Co. KG

T2 - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017

Y2 - 4 September 2017 through 8 September 2017

ER -

ID: 9088179