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

DOI10.1137/080732572MaRDI QIDQ2884575zbMATH OpenOpenAlexFDO

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

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)

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

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
• scientific article; zbMATH DE number 2079371 (Why is no real title available?)
• 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)