Improved approximation algorithms for minimum cost node-connectivity augmentation problems
type: Item
instance of: scholarly article
title: Improved approximation algorithms for minimum cost node-connectivity augmentation problems
zbMATH Open document ID: 1394.68443
author: Zeev Nutov
published in: Theory of Computing Systems
publication date: 2018-06-01T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6879940
zbMATH Keywords: node-connectivity augmentation
zbMATH Keywords: approximation algorithm
zbMATH Keywords: crossing biset family
MaRDI profile type: Publication
full work available at URL: s00224-017-9786-5
OpenAlex ID: W2620883502
cites work: A bad example for the iterative rounding method for mincost \(k\)-connected spanning subgraphs
cites work: A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
cites work: Approximation algorithms for minimum-cost \(k\)-\((S,T)\) connected digraphs
cites work: Approximating Rooted Steiner Networks
cites work: Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
cites work: An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
cites work: An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design
cites work: A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
cites work: An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem
cites work: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
cites work: Rooted \(k\)-connections in digraphs
cites work: Minimal edge-coverings of pairs of sets
cites work: An application of submodular flows
cites work: Approximating minimum cost source location problems with local vertex-connectivity demands
cites work: Approximating the generalized terminal backup problem via half-integral multiflow relaxation
cites work: Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
cites work: Q3128880
cites work: Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
cites work: A factor 2 approximation algorithm for the generalized Steiner network problem
cites work: Approximation algorithms for combinatorial problems
cites work: On the optimal vertex-connectivity augmentation
cites work: Improved Approximation Algorithms for Uniform Connectivity Problems
cites work: Approximating node connectivity problems via set covers
cites work: Approximating k-node Connected Subgraphs via Critical Graphs
cites work: Approximating Source Location and Star Survivable Network Problems
cites work: Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
cites work: Inapproximability of survivable networks
cites work: On the ratio of optimal integral and fractional covers
cites work: Approximating minimum-cost connectivity problems via uncrossable bifamilies
cites work: Approximating node-connectivity augmentation problems
cites work: Approximating subset \(k\)-connectivity problems
cites work: Approximating minimum-cost edge-covers of crossing biset-families
cites work: Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems
cites work: An approximation algorithm for minimum-cost vertex-connectivity problems
cites work: Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
cites work: Augmenting Undirected Node-Connectivity by One
DOI: 10.1007/S00224-017-9786-5
description: scientific article; zbMATH DE number 6879940