Derandomization through approximation, an NC algorithm for minimum cuts

DOI10.1145/195058.195241zbMATH Open1344.68276OpenAlexW2025526852MaRDI QIDQ2817641FDOQ2817641

Authors: David R. Karger, Rajeev Motwani 

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.195241

Recommendations

• An $\NC$ Algorithm for Minimum Cuts
• Approximating unweighted connectivity problems in parallel
• A new approach to the minimum cut problem
• scientific article; zbMATH DE number 437525
• scientific article; zbMATH DE number 18532

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (6)

• Approximating unweighted connectivity problems in parallel
• The probabilistic method yields deterministic parallel algorithms
• Low-diameter graph decomposition is in NC
• Global and fixed-terminal cuts in digraphs
• Beating the 2-approximation factor for global bicut
• An $\NC$ Algorithm for Minimum Cuts

This page was built for publication: Derandomization through approximation, an NC algorithm for minimum cuts

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