Approximating minimum-power edge-covers and 2,3-connectivity

DOI10.1016/J.DAM.2008.12.001zbMath1227.05211OpenAlexW2113064124MaRDI QIDQ1026146

Guy Kortsarz, Zeev Nutov

Publication date: 24 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.12.001

zbMATH Keywords

approximation algorithmswireless networksnode-connectivityedge-coverminimum power

Mathematics Subject Classification ID

Applications of graph theory (05C90) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (4)

Approximating activation edge-cover and facility location problems ⋮ Approximating minimum power edge-multi-covers ⋮ Unnamed Item ⋮ Improved approximation algorithms for minimum power covering problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Power optimization for connectivity problems
• An application of submodular flows
• Increasing the rooted connectivity of a digraph by one
• Approximating node connectivity problems via set covers
• Power assignment for \(k\)-connectivity in wireless ad hoc networks
• A primal-dual approximation algorithm for generalized Steiner network problems
• An 11/6-approximation algorithm for the network Steiner problem
• Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
• On Minimum Power Connectivity Problems
• Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
• Approximating Minimum-Power Degree and Connectivity Problems
• Approximating k-node Connected Subgraphs via Critical Graphs

This page was built for publication: Approximating minimum-power edge-covers and 2,3-connectivity