Improved approximations for relative survivable network design

DOI10.1007/978-3-031-49815-2_14MaRDI QIDQ6574948

Michael Dinitz, Ama Koranteng, Zeev Nutov, Guy Kortsarz

Publication date: 19 July 2024

zbMATH Keywords

fault tolerancenetwork design

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating fault-tolerant group-Steiner problems
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Maintaining the classes of 4-edge-connectivity in a graph on-line
• A primal-dual approximation algorithm for generalized Steiner network problems
• Compact cactus representations of all non-trivial min-cuts
• Fault-tolerant spanners
• Approximating the smallest k -edge connected spanning subgraph by LP-rounding
• Important Separators and Parameterized Algorithms
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
• Maintenance of 2- and 3-Edge-Connected Components of Graphs II
• Approximating Rooted Steiner Networks
• Flexible Graph Connectivity
• A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
• Fault Tolerant Spanners for General Graphs
• Efficient and Simple Algorithms for Fault-Tolerant Spanners
• The parameterized complexity of the survivable network design problem
• Relative survivable network design
• Epic fail: emulators can tolerate polynomially many edge faults for free

This page was built for publication: Improved approximations for relative survivable network design