Approximating minimum power covers of intersecting families and directed edge-connectivity problems

DOI10.1016/j.tcs.2010.03.009zbMath1207.68446OpenAlexW2037416519MaRDI QIDQ974743

Zeev Nutov

Publication date: 7 June 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.03.009

zbMATH Keywords

directed graphsapproximation algorithmsedge-connectivitywireless networksintersecting familiespower minimization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Survivable network activation problems ⋮ An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths ⋮ Approximating minimum power edge-multi-covers ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Improved approximation algorithms for minimum power covering problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Power optimization for connectivity problems
• On minimum power connectivity problems
• Increasing the rooted connectivity of a digraph by one
• Power assignment for \(k\)-connectivity in wireless ad hoc networks
• Energy-efficient wireless network design
• Matroid Intersection
• Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Approximating Steiner Networks with Node Weights
• Approximating Minimum-Power Degree and Connectivity Problems
• Algorithms - ESA 2003