An $\NC$ Algorithm for Minimum Cuts

DOI10.1137/S0097539794273083zbMath0870.68081WikidataQ56114901 ScholiaQ56114901MaRDI QIDQ4337444

Rajeev Motwani, David R. Karger

Publication date: 7 September 1997

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

zbMATH Keywords

minimum-cut problemweighted undirected graphsset-isolation problemsparse \(k\)- connectivity certificate

Mathematics Subject Classification ID

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

Related Items (8)

The vertex \(k\)-cut problem ⋮ On integer and bilevel formulations for the \(k\)-vertex cut problem ⋮ On the \(k\)-cut problem ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ Derived category automorphisms from mirror symmetry ⋮ A lower bound for the shortest path problem ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs

This page was built for publication: An $\NC$ Algorithm for Minimum Cuts