An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph

DOI10.1137/S0895480102405476zbMath1071.05047OpenAlexW2083007099MaRDI QIDQ4652620

Harold N. Gabow

Publication date: 28 February 2005

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

network designgraph connectivityapproximation algorithmsdepth-first searchedge connectivity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Communication networks in operations research (90B18) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (1)

Approximation algorithms for flexible graph connectivity

This page was built for publication: An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph