Approximating minimum-power degree and connectivity problems

DOI10.1007/S00453-009-9365-5zbMath1216.68045OpenAlexW2116995951MaRDI QIDQ547290

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

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

zbMATH Keywords

approximationpowerdegreegraphswireless\(k\)-connectivity

Mathematics Subject Classification ID

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

Related Items (3)

Approximating minimum power edge-multi-covers ⋮ Approximating Survivable Networks with Minimum Number of Steiner Points ⋮ Approximation algorithms for minimum power k backbone node r-connected subgraph problem in wireless sensor networks

Cites Work

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

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