A 22k-approximation algorithm for minimum power k edge disjoint st-paths

DOI10.1016/J.IPL.2024.106532MaRDI QIDQ6663517zbMATH OpenFDO

Authors Zeev Nutov

Publication date 14 January 2025

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2024.106532

zbMATH Keywords

approximation algorithmedge-disjoint st-pathsminimum powerwireless networks

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths
• On minimum power connectivity problems
• On Minimum Power Connectivity Problems
• Power Optimization for Connectivity Problems
• Power optimization for connectivity problems

Cites work

• Algorithmic Aspects of Minimum Energy Edge-Disjoint Paths in Wireless Networks
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths
• Approximating minimum power covers of intersecting families and directed edge-connectivity problems
• Approximating Steiner networks with node-weights
• Approximation algorithms for disjoint st-paths with minimum activation cost
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• scientific article; zbMATH DE number 68915 (Why is no real title available?)
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• Minimally k-connected graphs of low order and maximal size
• Minimum activation cost node-disjoint paths in graphs with bounded treewidth
• On extremal \(k\)-outconnected graphs
• On fixed cost k-flow problems
• On minimum power connectivity problems
• Power consumption in packet radio networks
• Power optimization for connectivity problems
• Survivable network design problems in wireless networks
• The maximal size of graphs with at most \(k\) edge-disjoint paths connecting any two adjacent vertices
• Über minimal n-fach zusammenhängende, unendliche Graphen und ein Extremalproblem. (On minimal n-fold connected infinite graphs and an extremal problem)

Cited in

(1)

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

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

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