An \NC Algorithm for Minimum Cuts

DOI10.1137/S0097539794273083MaRDI QIDQ4337444zbMATH OpenDBLPWikidataFDO

Authors David R. Karger, Rajeev Motwani

Publication date 7 September 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539794273083

zbMATH Keywords

minimum-cut problemset-isolation problemsparse \(k\)- connectivity certificateweighted undirected graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• Derandomization through approximation, an NC algorithm for minimum cuts
• Approximation algorithms for minimum \(K\)-cut
• scientific article; zbMATH DE number 7759280
• scientific article; zbMATH DE number 1234600
• A new approach to the minimum cut problem
• Computing minimum cuts by randomized search heuristics
• scientific article; zbMATH DE number 3999696
• Minimum Cuts of Simple Graphs in Almost Always Linear Time
• On computing minimum(s,t)-cuts in digraphs
• A simple minimum \(T\)-cut algorithm

Cited in

(17)

• Derived category automorphisms from mirror symmetry
• On the \(k\)-cut problem
• On integer and bilevel formulations for the \(k\)-vertex cut problem
• I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs
• The vertex \(k\)-cut problem
• Derandomization through approximation, an NC algorithm for minimum cuts
• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 177555 (Why is no real title available?)
• scientific article; zbMATH DE number 1318514 (Why is no real title available?)
• scientific article; zbMATH DE number 1559536 (Why is no real title available?)
• Bipartite perfect matching is in quasi-NC
• Low-diameter graph decomposition is in NC
• An optimal algorithm for the minimum edge cardinality cut surface problem
• A lower bound for the shortest path problem
• Breaking the n ^k barrier for minimum k -cut on simple graphs
• Color fault-tolerant spanners
• Graph connectivity and its augmentation: Applications of MA orderings

This page was built for publication: 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 Q4337444)