The Minimum Cut Problem
Jump to navigation
Jump to search
Internal
Overview
Given an undirected graph G = (V, E), compute a cut with the fewest number of crossing edges.
Applications:
- identify network bottleneck or weaknesses
- community detection in social networks
- image segmentation
Algorithms
Karger's Contraction Algorithm
Karger's Contraction Algorithm is an example of a randomized algorithm.