Approximating minimum-power degree and connectivity problems

DOI10.1007/S00453-009-9365-5zbMATH Open1216.68045OpenAlexW2116995951MaRDI QIDQ547290FDOQ547290

Authors: Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko 

Publication date: 1 July 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9365-5

Recommendations

• Approximating Minimum-Power Degree and Connectivity Problems
• Approximate min-power strong connectivity
• Approximating minimum-power edge-covers and 2,3-connectivity
• Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
• Approximating minimum power covers of intersecting families and directed edge-connectivity problems
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Approximating minimum size \{1,2\}-connected networks

zbMATH Keywords

graphspowerapproximationdegree\(k\)-connectivitywireless

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Cites Work

• Approximation algorithms for combinatorial problems
• The dense \(k\)-subgraph problem
• Network lifetime and power assignment in ad hoc wireless networks
• Power optimization for connectivity problems
• Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
• Power assignment for \(k\)-connectivity in wireless ad hoc networks
• On Minimum Power Connectivity Problems

Cited In (10)

• On minimum power connectivity problems
• Power Optimization for Connectivity Problems
• Survivable network design problems in wireless networks
• Minimizing the number of max-power users in ad-hoc wireless networks with minimum node degree requirements
• Power assignment for \(k\)-connectivity in wireless ad hoc networks
• Approximation algorithms for minimum power \(k\) backbone node \(r\)-connected subgraph problem in wireless sensor networks
• On Minimum Power Connectivity Problems
• Approximating Minimum-Power Degree and Connectivity Problems
• Improved approximation algorithms for minimum power covering problems
• Approximating minimum-power edge-covers and 2,3-connectivity

This page was built for publication: Approximating minimum-power degree and connectivity problems

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