The Minimum Cut Problem

From NovaOrdis Knowledge Base
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.

Karger's Contraction Algorithm