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

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

zbMATH Keywords

linear programnetwork designgraph connectivityapproximation algorithmsedge connectivityLP-roundingMAX SNP-hardness

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Connectivity (05C40)

Related Items

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