Faster Algorithms for Edge Connectivity via Random 2-Out Contractions

DOI10.1137/1.9781611975994.77MaRDI QIDQ5146849zbMATH OpenOpenAlexFDO

Authors Mohsen Ghaffari, Krzysztof Nowicki, Mikkel Thorup

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.00844

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(15)

• Near-optimal scheduling in the congested clique
• Faster connectivity in low-rank hypergraphs via expander decomposition
• Faster cut sparsification of weighted graphs
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• Random-Edge Is Slower Than Random-Facet on Abstract Cubes
• Deterministic Edge Connectivity in Near-Linear Time
• scientific article; zbMATH DE number 7651198 (Why is no real title available?)
• Finding a small vertex cut on distributed networks
• Near-optimal distributed computation of small vertex cuts
• Minimum cut in \(O(m \log^2 n)\) time
• Streaming edge coloring with asymptotically optimal colors
• Massively parallel computation in a heterogeneous regime
• A parameterized algorithm for vertex and edge connectivity of embedded graphs
• Efficient contractions of dynamic graphs -- with applications
• Cut-query algorithms with few rounds

This page was built for publication: Faster Algorithms for Edge Connectivity via Random 2-Out Contractions

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