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

DOI10.1016/J.TCS.2010.03.009zbMATH Open1207.68446OpenAlexW2037416519MaRDI QIDQ974743FDOQ974743

Authors 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

approximation algorithmsdirected graphswireless networksedge-connectivityintersecting familiespower minimization

Mathematics Subject Classification ID

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

Recommendations

• Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
• Power optimization for connectivity problems
• Power Optimization for Connectivity Problems
• Approximating minimum-power edge-covers and 2,3-connectivity
• On minimum power connectivity problems

Cites work

• scientific article; zbMATH DE number 437545 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 863470 (Why is no real title available?)
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
• Approximating Minimum-Power Degree and Connectivity Problems
• Approximating Steiner Networks with Node Weights
• Energy-efficient wireless network design
• Increasing the rooted connectivity of a digraph by one
• Matroid Intersection
• Network lifetime and power assignment in ad hoc wireless networks
• On minimum power connectivity problems
• Power assignment for \(k\)-connectivity in wireless ad hoc networks
• Power optimization for connectivity problems

Cited in

(10)

• Listing minimal edge-covers of intersecting families with applications to connectivity problems
• An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths
• Approximating minimum-power degree and connectivity problems
• Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
• Approximating minimum-cost edge-covers of crossing biset-families
• Improved approximation algorithms for minimum power covering problems
• Survivable network activation problems
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
• A \(2\sqrt{2k}\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths

This page was built for publication: Approximating minimum power covers of intersecting families and directed edge-connectivity problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974743)