Approximating the smallest k-edge connected spanning subgraph by LP-rounding
From MaRDI portal
Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding (scientific article; zbMATH DE number 5818748)
Recommendations
- Approximating the smallest k-edge connected spanning subgraph by LP-rounding
- Iterated rounding algorithms for the smallest k-edge connected spanning subgraph
- k-edge-connectivity: approximation and LP relaxation
- An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph
- scientific article; zbMATH DE number 2079371
Cites work
- A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Algorithms for a network design problem with crossing supermodular demands
- An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Approximating the Minimum Equivalent Digraph
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Improved Approximation Algorithms for Uniform Connectivity Problems
- On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs
- Random sampling in cut, flow, and network design problems
- Special edges, and approximating the smallest directed k-edge connected spanning subgraph
- Submodular functions in graph theory
- The traveling salesman problem on a graph and some related integer polyhedra
Cited in
(38)- Sparse certificates for 2-connectivity in directed graphs
- On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
- A bad example for the iterative rounding method for mincost k-connected spanning subgraphs
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Bulk-robust combinatorial optimization
- An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
- Box-total dual integrality and edge-connectivity
- A rounding by sampling approach to the minimum size \(k\)-arc connected subgraph problem
- Iterated rounding algorithms for the smallest k-edge connected spanning subgraph
- Approximating the smallest k-edge connected spanning subgraph by LP-rounding
- scientific article; zbMATH DE number 6696497 (Why is no real title available?)
- k-edge-connectivity: approximation and LP relaxation
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Flexible Graph Connectivity
- How to Secure Matchings Against Edge Failures
- A Spectral Approach to Network Design
- How to Secure Matchings against Edge Failures
- Multicommodity flow in trees: packing via covering and iterated relaxation
- An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph
- An Improved Approximation Algorithm for the Matching Augmentation Problem
- Color-avoiding connected spanning subgraphs with minimum number of edges
- A (1.5+)-approximation algorithm for weighted connectivity augmentation
- Improved approximations for relative survivable network design
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- An O( n)-approximation algorithm for (p, q)-flexible graph connectivity via independent rounding
- An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover
- Better-than-2 approximations for weighted tree augmentation and applications to Steiner tree
- Improved approximation algorithms for covering pliable set families and flexible graph connectivity
- Dual-based approximation algorithms for cut-based network connectivity problems
- Improved approximations for flexible network design
- Approximating total effective resistance minimization with small budget
- Approximating total effective resistance minimization with small budget
- Bicriteria approximation for k-edge-connectivity
- Fault-tolerant matroid bases
- Light edge fault tolerant graph spanners
- Approximation schemes for planar graph connectivity problems
- Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
This page was built for publication: Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057092)
