Augmenting undirected connectivity in RNC and in randomized Õ(n3) time

DOI10.1145/195058.195425zbMath1345.68169OpenAlexW1982100369MaRDI QIDQ2817659

András A. Benczúr

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195425

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Randomized algorithms (68W20)

Related Items (4)

A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem ⋮ Separating maximally violated comb inequalities in planar graphs ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ A fast algorithm for cactus representations of minimum cuts

This page was built for publication: Augmenting undirected connectivity in RNC and in randomized Õ(n³) time