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

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, 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