Improved approximations for relative survivable network design
From MaRDI portal
Publication:6574948
DOI10.1007/978-3-031-49815-2_14MaRDI QIDQ6574948FDOQ6574948
Authors: Michael Dinitz, Ama Koranteng, Guy Kortsarz, Zeev Nutov
Publication date: 19 July 2024
Cites Work
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Fault-tolerant spanners
- Fault tolerant spanners for general graphs
- Important separators and parameterized algorithms
- A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Maintenance of 2- and 3-Edge-Connected Components of Graphs II
- Approximating rooted Steiner networks
- Approximating fault-tolerant group-Steiner problems
- Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
- A primal-dual approximation algorithm for generalized Steiner network problems
- Multiple-edge-fault-tolerant approximate shortest-path trees
- Maintaining the classes of 4-edge-connectivity in a graph on-line
- Title not available (Why is that?)
- Compact cactus representations of all non-trivial min-cuts
- Efficient and Simple Algorithms for Fault-Tolerant Spanners
- Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
- A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
- Flexible Graph Connectivity
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6574948)