Improved approximations for flexible network design

DOI10.4230/LIPICS.ESA.2024.74MaRDI QIDQ7253140zbMATH OpenFDO

Authors Dylan Hyatt-Denesik, Afrouz Jabal Ameli, Laura Sanità

Publication date 26 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2024.74

zbMATH Keywords

approximation algorithmsflexible connectivitynetwork design

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A 4/3 approximation for 2-vertex-connectivity
• A factor 2 approximation algorithm for the generalized Steiner network problem
• An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Approximation algorithms for network design in non-uniform fault models
• Biconnectivity approximations and graph carvings
• Fault-tolerant edge-disjoint \(s\)-\(t\) paths -- beyond uniform faults
• Flexible graph connectivity
• scientific article; zbMATH DE number 1263175 (Why is no real title available?)
• scientific article; zbMATH DE number 1305417 (Why is no real title available?)
• Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
• Improved Approximation for Two-Edge-Connectivity
• 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

Cited in

(1)

• Improved approximation algorithms for capacitated network design and flexible graph connectivity

This page was built for publication: Improved approximations for flexible network design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7253140)