An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths

DOI10.1007/978-3-031-36978-0_23arXiv2208.09373OpenAlexW4384789345MaRDI QIDQ6149053

Zeev Nutov

Publication date: 12 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

wireless networksminimum poweredge disjoint \(st\)-paths

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• On fixed cost \(k\)-flow problems
• Power optimization for connectivity problems
• On minimum power connectivity problems
• Approximating minimum power covers of intersecting families and directed edge-connectivity problems
• Power consumption in packet radio networks
• Detecting high log-densities
• Survivable Network Activation Problems
• Minimum Activation Cost Node-Disjoint Paths in Graphs with Bounded Treewidth
• Approximation Algorithms for Disjoint st-Paths with Minimum Activation Cost
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Approximating Steiner Networks with Node-Weights
• Algorithmic Aspects of Minimum Energy Edge-Disjoint Paths in Wireless Networks

This page was built for publication: An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths