Approximating Minimum-Power Degree and Connectivity Problems

DOI10.1007/978-3-540-78773-0_37MaRDI QIDQ5458548zbMATH OpenOpenAlexFDO

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

Publication date 15 April 2008

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

Full work available at URL https://doi.org/10.1007/978-3-540-78773-0_37

Mathematics Subject Classification ID

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

Recommendations

• Approximating minimum-power degree and connectivity problems
• Power optimization for connectivity problems
• Approximating minimum-power edge-covers and 2,3-connectivity

Cited in

(13)

• On minimum power connectivity problems
• Approximating minimum power covers of intersecting families and directed edge-connectivity problems
• Power Optimization for Connectivity Problems
• On min-power Steiner tree
• Wireless network design via 3-decompositions
• Minimizing the number of max-power users in ad-hoc wireless networks with minimum node degree requirements
• Survivable network design problems in wireless networks
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• On Minimum Power Connectivity Problems
• Approximating minimum-power degree and connectivity problems
• Improved approximation algorithms for minimum power covering problems
• On the Power of Nodes of Degree Four in the Local Max-Cut Problem
• 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 Q5458548)