Approximating node connectivity problems via set covers

DOI10.1007/s00453-003-1027-4zbMath1058.68082OpenAlexW2178484001MaRDI QIDQ1424250

Zeev Nutov, Guy Kortsarz

Publication date: 11 March 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-003-1027-4

zbMATH Keywords

approximation algorithmsmetric costs\(k\)-vertex connected spanning subgraph

Mathematics Subject Classification ID

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

Related Items (24)

Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs ⋮ Approximating subset \(k\)-connectivity problems ⋮ On Directed Steiner Trees with Multiple Roots ⋮ Power optimization for connectivity problems ⋮ Survivable network activation problems ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ On a partition LP relaxation for min-cost 2-node connected spanning subgraphs ⋮ Approximating node-connectivity augmentation problems ⋮ Relay placement for fault tolerance in wireless networks in higher dimensions ⋮ Approximating bounded-degree spanning trees and connected factors with leaves ⋮ Approximating k-Connected m-Dominating Sets ⋮ Degree constrained node-connectivity problems ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ On minimum power connectivity problems ⋮ Approximating survivable networks with \(\beta \)-metric costs ⋮ Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems ⋮ A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius ⋮ Approximating minimum-power edge-covers and 2,3-connectivity

This page was built for publication: Approximating node connectivity problems via set covers