Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
From MaRDI portal
Publication:5084628
DOI10.1287/ijoc.2020.1045zbMath1492.90031arXiv1706.03177OpenAlexW2984733936MaRDI QIDQ5084628
René van Bevern, Matthias Bentert, Pavel V. Smirnov, Rolf Niedermeier, André Nichterlein
Publication date: 28 June 2022
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.03177
experimental comparisoncolor-codingapproximation hardnessconnected spanning subgraphsparameterized complexity analysismonitoring areasreconnecting sensor networksparameterization above lower bounds
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Rural postman parameterized by the number of components of required edges
- Fundamentals of parameterized complexity
- Strong computational lower bounds via parameterized complexity
- Experiments on data reduction for optimal domination in networks
- Power assignment in radio networks with two power levels
- Power consumption in packet radio networks
- Which problems have strongly exponential complexity?
- Parameterizing edge modification problems above lower bounds
- Variable neighborhood search variants for min-power symmetric connectivity problem
- Minimizing the number of max-power users in ad-hoc wireless networks with minimum node degree requirements
- Exact algorithms for the minimum power symmetric connectivity problem in wireless networks
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A new view on rural postman based on Eulerian extension and matching
- Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
- A completeness theory for polynomial (Turing) kernelization
- Parametrized complexity theory.
- On Multiway Cut Parameterized above Lower Bounds
- The Design of Approximation Algorithms
- From Few Components to an Eulerian Graph by Adding Arcs
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Color-coding
- Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
- Kernelization
- Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
- An average case analysis of the minimum spanning tree heuristic for the power assignment problem
- On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem
- Parameterized Algorithms
- Parameterized complexity of min-power asymmetric connectivity
- On the complexity of \(k\)-SAT
- On approximate data reduction for the Rural Postman Problem: Theory and experiments
- A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments
