Approximating the smallest k -edge connected spanning subgraph by LP-rounding
From MaRDI portal
Publication:3057092
DOI10.1002/net.20289zbMath1205.05125OpenAlexW4240507476WikidataQ101127553 ScholiaQ101127553MaRDI QIDQ3057092
Éva Tardos, Harold N. Gabow, Michel X. Goemans, David P. Williamson
Publication date: 24 November 2010
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.20289
linear programnetwork designgraph connectivityapproximation algorithmsedge connectivityLP-roundingMAX SNP-hardness
Related Items (16)
An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ Flexible Graph Connectivity ⋮ Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ A Spectral Approach to Network Design ⋮ The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm ⋮ Approximation algorithms for flexible graph connectivity ⋮ Color-avoiding connected spanning subgraphs with minimum number of edges ⋮ Box-total dual integrality and edge-connectivity ⋮ How to Secure Matchings against Edge Failures ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Simpler analysis of LP extreme points for traveling salesman and survivable network design problems ⋮ Dual-based approximation algorithms for cut-based network connectivity problems ⋮ On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem ⋮ Bulk-robust combinatorial optimization ⋮ How to Secure Matchings Against Edge Failures
Cites Work
- Unnamed Item
- Submodular functions in graph theory
- A factor 2 approximation algorithm for the generalized Steiner network problem
- On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Random Sampling in Cut, Flow, and Network Design Problems
- The traveling salesman problem on a graph and some related integer polyhedra
- A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
- Algorithms for a network design problem with crossing supermodular demands
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Approximating the Minimum Equivalent Digraph
- Improved Approximation Algorithms for Uniform Connectivity Problems
- An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph
This page was built for publication: Approximating the smallest k -edge connected spanning subgraph by LP-rounding