Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks

DOI10.1007/978-3-319-72751-6_3MaRDI QIDQ5056047zbMATH OpenOpenAlexFDO

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

Publication date 9 December 2022

Published in Algorithms for Sensor Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-72751-6_3

zbMATH Keywords

approximation hardnesscolor codingdata reductionmonitoring areas and backbonesparameterization above lower boundsparameterized complexityspanning trees

Mathematics Subject Classification ID

Wireless sensor networks as related to computer science (68M18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
• Exact algorithms for the minimum power symmetric connectivity problem in wireless networks
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Energy efficient and robust CSIP algorithm in distributed wireless sensor networks
• Algorithms for \(k\)-fault tolerant power assignments in wireless sensor networks

Cites work

• A new view on rural postman based on Eulerian extension and matching
• Approximation algorithms for mixed, windy, and capacitated arc routing problems
• Average parameterization and partial kernelization for computing medians
• Color-coding
• Exact algorithms for the minimum power symmetric connectivity problem in wireless networks
• From few components to an Eulerian graph by adding ARCS
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 1500550 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem
• On the complexity of k-SAT
• Parameterized algorithmics and computational experiments for finding 2-clubs
• Power assignment in radio networks with two power levels
• Research in Computational Molecular Biology
• Rural postman parameterized by the number of components of required edges
• Survivable network design problems in wireless networks
• The Power of Linear-Time Data Reduction for Maximum Matching
• Two-layer planarization parameterized by feedback edge set
• Variable neighborhood search variants for min-power symmetric connectivity problem
• Which problems have strongly exponential complexity?

Cited in

(3)

• Polynomial-time data reduction for weighted problems beyond additive goal functions
• Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
• On approximate data reduction for the Rural Postman Problem: Theory and experiments

Describes a project that uses

Uses Software

• QNet

This page was built for publication: Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056047)