Tight approximation algorithm for connectivity augmentation problems
type: Item
instance of: scholarly article
title: Tight approximation algorithm for connectivity augmentation problems
zbMATH Open document ID: 1182.68363
author: Guy Kortsarz
author: Zeev Nutov
published in: Journal of Computer and System Sciences
publication date: 2008-06-26T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5293384
zbMATH Keywords: connectivity augmentation
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
full work available at URL: j.jcss.2007.05.002
OpenAlex ID: W2031552172
cites work: Covering symmetric supermodular functions by graphs
cites work: Approximation Algorithms for Directed Steiner Problems
cites work: Network design via iterative rounding of setpair relaxations
cites work: Approximation algorithms for network design with metric costs
cites work: Design networks with bounded pairwise distance
cites work: Augmenting Graphs to Meet Edge-Connectivity Requirements
cites work: Minimal edge-coverings of pairs of sets
cites work: Polylogarithmic inapproximability
cites work: Q4472504
cites work: Independence free graphs and vertex connectivity augmentation
cites work: A factor 2 approximation algorithm for the generalized Steiner network problem
cites work: Q2753740
cites work: On shredders and vertex connectivity augmentation
cites work: A Reduction Method for Edge-Connectivity in Graphs
cites work: On the minimum local-vertex-connectivity augmentation in graphs
cites work: Approximating connectivity augmentation problems
cites work: Approximating rooted connectivity augmentation problems
cites work: Q4527015
cites work: Edge-connectivity augmentation problems
cites work: An analysis of the greedy algorithm for the submodular set covering problem
DOI: 10.1016/J.JCSS.2007.05.002
description: scientific article; zbMATH DE number 5293384