Approximating the smallest k -edge connected spanning subgraph by LP-rounding
From MaRDI portal
Publication:3057092
DOI10.1002/net.20289zbMath1205.05125WikidataQ101127553 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 program; network design; graph connectivity; approximation algorithms; edge connectivity; LP-rounding; MAX SNP-hardness
Related Items
Flexible Graph Connectivity, A Spectral Approach to Network Design, How to Secure Matchings against Edge Failures, How to Secure Matchings Against Edge Failures, An Improved Approximation Algorithm for the Matching Augmentation Problem, Approximation algorithms for flexible graph connectivity, Color-avoiding connected spanning subgraphs with minimum number of edges, Multicommodity flow in trees: packing via covering and iterated relaxation, Dual-based approximation algorithms for cut-based network connectivity problems, Simpler analysis of LP extreme points for traveling salesman and survivable network design problems, Sparse certificates for 2-connectivity in directed graphs, On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem, The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm, Bulk-robust combinatorial optimization, Box-total dual integrality and edge-connectivity, Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs
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