Approximation algorithms for flexible graph connectivity
DOI10.1007/s10107-023-01961-5arXiv2202.13298MaRDI QIDQ6120848
Sylvia Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur
Publication date: 21 February 2024
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2202.13298
combinatorial optimizationnetwork designapproximation algorithmsreliability of networksedge-connectivity of graphs
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Connectivity (05C40) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx) Robustness in mathematical programming (90C17)
Cites Work
- 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
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A primal-dual approximation algorithm for generalized Steiner network problems
- Approximability of capacitated network design
- Conservative weightings and ear-decompositions of graphs
- Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph
- Approximating the smallest k -edge connected spanning subgraph by LP-rounding
- Biconnectivity approximations and graph carvings
- Computing All Small Cuts in an Undirected Network
- An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph
- Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
- A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
- Flexible Graph Connectivity
This page was built for publication: Approximation algorithms for flexible graph connectivity
