Parameterized complexity of min-power asymmetric connectivity

DOI10.1007/s00224-020-09981-wzbMath1503.68080arXiv2005.14620OpenAlexW3032876419MaRDI QIDQ5918282

Tomohiro Koana, André Nichterlein, Christian Hofer, Matthias Bentert, Roman Haag

Publication date: 11 June 2021

Published in: Lecture Notes in Computer Science, Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.14620

zbMATH Keywords

parameterized algorithmicsmonitoring areasreconnecting sensor networks

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Signed and weighted graphs (05C22) Parameterized complexity, tractability and kernelization (68Q27) Wireless sensor networks as related to computer science (68M18)

Related Items (3)

Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions

Cites Work

• Fundamentals of parameterized complexity
• Parameterizing by the number of numbers
• Power assignment in radio networks with two power levels
• Which problems have strongly exponential complexity?
• A new view on rural postman based on Eulerian extension and matching
• Approximate Min-Power Strong Connectivity
• Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
• Algorithms - ESA 2003
• On the complexity of \(k\)-SAT
• 1.61-approximation for min-power strong connectivity with two power levels

This page was built for publication: Parameterized complexity of min-power asymmetric connectivity