FANDOM


This is an alternate formulation to the Max Flow Problem.

  • We want to remove some edges from the graph such that after removing the edges, there is no path from s to t.
  • The cost of removing e is equal to c(e).
  • The minimum cut problem is to find a cut with minimum total cost.

Theorem: Minimum Cut = Max Flow

Since we know the max flow, we can use the Residual Graph to find the min cut.

Algorithm Edit

Steps:

  1. Mark all nodes reachable from S. Call this set of reachable nodes A.
  2. Now separate these nodes from the others. Cut edges going from A to V - A
  3. Now look at the original graph and find the cut.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.