Power optimization for connectivity problems

DOI10.1007/S10107-006-0057-5zbMath1192.90173OpenAlexW2162071758MaRDI QIDQ877193

Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Mohammad Taghi Hajiaghayi

Publication date: 19 April 2007

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0057-5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (16)

Approximating activation edge-cover and facility location problems ⋮ Survivable network activation problems ⋮ Minimum shared‐power edge cut ⋮ An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths ⋮ Improved approximation algorithms for label cover problems ⋮ Approximating minimum power edge-multi-covers ⋮ Approximating minimum-power degree and connectivity problems ⋮ On minimum power connectivity problems ⋮ Approximating minimum power covers of intersecting families and directed edge-connectivity problems ⋮ Unnamed Item ⋮ Wireless network design via 3-decompositions ⋮ Improved approximation algorithms for minimum power covering problems ⋮ Approximating Steiner Networks with Node Weights ⋮ New Results on the Complexity of the Max- and Min-Rep Problems ⋮ A \(2\sqrt{2k}\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths ⋮ Approximating minimum-power edge-covers and 2,3-connectivity

Cites Work

• An application of submodular flows
• Optimization, approximation, and complexity classes
• Approximating node connectivity problems via set covers
• Power consumption in packet radio networks
• Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
• Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks
• Approximation algorithm for k-node connected subgraphs via critical graphs
• Biconnectivity approximations and graph carvings
• A Parallel Repetition Theorem
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
• Improved Approximation Algorithms for Uniform Connectivity Problems
• Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• On the hardness of approximating spanners

This page was built for publication: Power optimization for connectivity problems