Improved approximation algorithms for min-cost connectivity augmentation problems

DOI10.1007/978-3-319-34171-2_23MaRDI QIDQ5740195zbMATH OpenOpenAlexFDO

Authors Zeev Nutov

Publication date 25 July 2016

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-34171-2_23

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• Approximating subset \(k\)-connectivity problems
• Approximating subset k-connectivity problems
• Tight Approximation Algorithm for Connectivity Augmentation Problems
• Tight approximation algorithm for connectivity augmentation problems

Cites work

• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• 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
• A bad example for the iterative rounding method for mincost k-connected spanning subgraphs
• A factor 2 approximation algorithm for the generalized Steiner network problem
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
• An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
• An O(k^3 n)-approximation algorithm for vertex-connectivity survivable network design
• An application of submodular flows
• An approximation algorithm for minimum-cost vertex-connectivity problems
• Approximating k-node Connected Subgraphs via Critical Graphs
• Approximating minimum cost source location problems with local vertex-connectivity demands
• Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Approximating minimum-cost edge-covers of crossing biset-families
• Approximating node connectivity problems via set covers
• Approximating node-connectivity augmentation problems
• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• Augmenting undirected node-connectivity by one
• Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
• Improved Approximation Algorithms for Uniform Connectivity Problems
• Inapproximability of survivable networks
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• Minimal edge-coverings of pairs of sets
• On the optimal vertex-connectivity augmentation
• Rooted \(k\)-connections in digraphs

Cited in

(11)

• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• Approximating subset \(k\)-connectivity problems
• Approximating node-connectivity augmentation problems
• Approximating subset k-connectivity problems
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
• Minimum Cardinality Point-to-point Connectivity Augmentation Problem
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• Approximating Minimum Cost Connectivity Orientation and Augmentation
• NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems
• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• Fixed-parameter algorithms for minimum cost edge-connectivity augmentation

This page was built for publication: Improved approximation algorithms for min-cost connectivity augmentation problems

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