Augmenting Undirected Edge Connectivity in Õ(n2) Time

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

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

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

Recommendations

• scientific article; zbMATH DE number 1303592
• scientific article; zbMATH DE number 1256720
• Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs

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 (8)

• 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
• Augmenting undirected connectivity in RNC and in randomized \(\tilde{O}(n^3)\) time
• 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)