Iterated rounding algorithms for the smallest k-edge connected spanning subgraph

DOI10.1137/080732572zbMATH Open1243.68225OpenAlexW2083162966MaRDI QIDQ2884575FDOQ2884575

Authors: Harold N. Gabow, Suzanne R. Gallagher 

Publication date: 30 May 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080732572

Recommendations

• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
• Approximating k-node Connected Subgraphs via Critical Graphs
• An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph

zbMATH Keywords

linear programmingapproximation algorithmsgraph algorithmsnetwork designgraph connectivityedge connectivity

Mathematics Subject Classification ID

Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40)

Cited In (13)

• \(k\)-edge-connectivity: approximation and LP relaxation
• Flexible graph connectivity
• Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
• A bad example for the iterative rounding method for mincost \(k\)-connected spanning subgraphs
• Title not available (Why is that?)
• Special edges, and approximating the smallest directed \(k\)-edge connected spanning subgraph
• An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• A rounding by sampling approach to the minimum size \(k\)-arc connected subgraph problem
• Flexible Graph Connectivity
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• Multicommodity flow in trees: packing via covering and iterated relaxation

This page was built for publication: Iterated rounding algorithms for the smallest \(k\)-edge connected spanning subgraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2884575)