Augmenting Undirected Edge Connectivity in Õ(n2) Time

DOI10.1006/JAGM.2000.1093MaRDI QIDQ4512571zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• scientific article; zbMATH DE number 1303592
• scientific article; zbMATH DE number 1256720
• Deterministic 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

Cited in

(8)

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

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)