Approximation algorithms for vertex-connectivity augmentation on the cycle
type: Item
instance of: scholarly article
title: Approximation algorithms for vertex-connectivity augmentation on the cycle
DOI: 10.1007/978-3-030-92702-8_1
author: Waldo Gálvez
author: Francisco Sanhueza-Matamala
author: José A. Soto
publication date: 2022-10-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/2111.02234
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W27
zbMATH DE Number: 7603881
zbMATH Keywords: approximation algorithms
zbMATH Keywords: connectivity augmentation
zbMATH Keywords: cycle augmentation
zbMATH Keywords: network design
MaRDI profile type: Publication
OpenAlex ID: W4285524729
cites work: Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
cites work: A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
cites work: Parameterized Algorithms to Preserve Connectivity
cites work: Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
cites work: Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
cites work: Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
cites work: Q4938792
cites work: On the integrality ratio for tree augmentation
cites work: A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
cites work: A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
cites work: Q4607935
cites work: Approximation Algorithms for Several Graph Augmentation Problems
cites work: On the cycle augmentation problem: hardness and approximation algorithms
cites work: Q3128880
cites work: Improved approximation for tree augmentation: saving by rewiring
cites work: Approximation Algorithms for Graph Augmentation
cites work: Biconnectivity approximations and graph carvings
cites work: Hardness of Approximation for Vertex-Connectivity Network Design Problems
cites work: A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
cites work: LP-relaxations for tree augmentation
cites work: Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
cites work: Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
cites work: An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
cites work: 2-node-connectivity network design
cites work: A 4 + ε approximation for k-connected subgraphs
cites work: On the tree augmentation problem
cites work: Recognition of Circle Graphs
cites work: Augmenting Undirected Node-Connectivity by One
description: scientific article; zbMATH DE number 7603881