Flexible graph connectivity

DOI10.1007/s10107-021-01664-9OpenAlexW3169981244MaRDI QIDQ2118137

Moritz Mühlenthaler, David Adjiashvili, Felix Hommelsheim

Publication date: 22 March 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-021-01664-9

zbMATH Keywords

robustnessgraph algorithmsnetwork designgraph connectivityapproximation algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Connectivity (05C40)

Related Items

Flexible Graph Connectivity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
• A factor 2 approximation algorithm for the generalized Steiner network problem
• LP-relaxations for tree augmentation
• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• Approximability of capacitated network design
• Bulk-robust combinatorial optimization
• Capacitated Network Design on Undirected Graphs
• Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
• Flexible Graph Connectivity
• Time-Expanded Packings
• Improved approximation for tree augmentation: saving by rewiring
• An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph