Approximating node connectivity problems via set covers

DOI10.1007/S00453-003-1027-4MaRDI QIDQ1424250zbMATH OpenOpenAlexFDO

Authors Guy Kortsarz, Zeev Nutov

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)

Recommendations

• scientific article; zbMATH DE number 1670542
• Approximation Algorithms for Network Design with Metric Costs
• Approximating k-node Connected Subgraphs via Critical Graphs
• An almost \(O(\log k)\)-approximation for \(k\)-connected subgraphs
• Approximating minimum-cost connectivity problems via uncrossable bifamilies

Cited in

(40)

• On rooted node-connectivity problems
• Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs
• Power optimization for connectivity problems
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Approximation Algorithms for Network Design with Metric Costs
• Approximating k-node Connected Subgraphs via Critical Graphs
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• On \(k\)-connectivity problems with sharpened triangle inequality
• Approximating survivable networks with \(\beta \)-metric costs
• Approximating node-connectivity augmentation problems
• On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
• Approximating minimum-power edge-covers and 2,3-connectivity
• Approximation algorithm for \(k\)-node connected subgraphs via critical graphs
• Approximating bounded-degree spanning trees and connected factors with leaves
• Fast distributed approximation for TAP and 2-edge-connectivity
• Approximating subset \(k\)-connectivity problems
• An almost \(O(\log k)\)-approximation for \(k\)-connected subgraphs
• Improved approximation algorithms for min-cost connectivity augmentation problems
• Connected Set Cover Problem and Its Applications
• Approximation algorithms for connected graph factors of minimum weight
• Approximation algorithms for minimum-cost \(k\)-\((S,T)\) connected digraphs
• Survivable network activation problems
• Relay placement for fault tolerance in wireless networks in higher dimensions
• scientific article; zbMATH DE number 2080258 (Why is no real title available?)
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• Approximating k-Connected m-Dominating Sets
• Approximating subset \(k\)-connectivity problems
• scientific article; zbMATH DE number 1670542 (Why is no real title available?)
• A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
• On minimum power connectivity problems
• Complexity and approximation of the connected set-cover problem
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• On directed Steiner trees with multiple roots
• 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
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Degree constrained node-connectivity problems
• A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
• Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs

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

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