Approximating the smallest k -edge connected spanning subgraph by LP-rounding

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

zbMATH Keywords

linear program; network design; graph connectivity; approximation algorithms; edge connectivity; LP-rounding; MAX SNP-hardness

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C40: Connectivity

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