Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph

DOI10.1137/080732572zbMath1243.68225OpenAlexW2083162966MaRDI QIDQ2884575

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 programminggraph algorithmsnetwork designgraph connectivityapproximation algorithmsedge connectivity

Mathematics Subject Classification ID

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

Related Items (5)

Flexible Graph Connectivity ⋮ Approximation algorithms for flexible graph connectivity ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Flexible graph connectivity

This page was built for publication: Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph