Augmenting Undirected Edge Connectivity in Õ(n2) Time

DOI10.1006/JAGM.2000.1093zbMATH Open0962.68135OpenAlexW2608846391MaRDI QIDQ4512571FDOQ4512571

David R. Karger, András A. Benczúr

Publication date: 13 June 2001

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.2000.1093

zbMATH Keywords

edge connectivity augmentation problemsundirected edge splitting

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Connectivity (05C40)

Cited In (7)

• Provision of maximum connectivity resiliency with minimum cost to telecommunication networks through third‐party networks
• Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
• Minimum degree orderings
• Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness
• Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
• On budget-constrained flow improvement.
• Minimizing a monotone concave function with laminar covering constraints

This page was built for publication: Augmenting Undirected Edge Connectivity in Õ(n2) Time

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