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 (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