Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks

DOI10.1007/978-3-319-72751-6_3zbMath1503.68026OpenAlexW2624846542MaRDI QIDQ5056047

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

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

data reductionparameterized complexityspanning treesapproximation hardnesscolor codingmonitoring areas and backbonesparameterization above lower bounds

Mathematics Subject Classification ID

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

Related Items

Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments, On approximate data reduction for the Rural Postman Problem: Theory and experiments, Polynomial-time data reduction for weighted problems beyond additive goal functions, Parameterized complexity of min-power asymmetric connectivity

Uses Software

• QNet

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rural postman parameterized by the number of components of required edges
• Fundamentals of parameterized complexity
• Two-layer planarization parameterized by feedback edge set
• Average parameterization and partial kernelization for computing medians
• Power assignment in radio networks with two power levels
• Which problems have strongly exponential complexity?
• Variable neighborhood search variants for min-power symmetric connectivity problem
• Exact algorithms for the minimum power symmetric connectivity problem in wireless networks
• A new view on rural postman based on Eulerian extension and matching
• From Few Components to an Eulerian Graph by Adding Arcs
• Color-coding
• The Power of Linear-Time Data Reduction for Maximum Matching
• Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
• On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem
• Research in Computational Molecular Biology
• Parameterized aspects of triangle enumeration
• On the complexity of \(k\)-SAT