# Tag Info

### Residual Graph in Maximum Flow

The intuition behing the residual graph in the Maximum flow problem is very well presented in this lecture. The explanation goes as follows. Suppose that we are trying to solve the maximum flow ...
• 3,734
Accepted

### How to find max flow in a graph after decrementing an edge capacity?

If the capacity of edge $c(e') \ge f(e') + 1$ i.e. the max flow remains the same, there is no chance max flow increase, as it would increased without decreasing $c(e')$. Suppose that $c(e') = f(e')$ (...
• 1,189
Accepted

• 29.5k

### P=NP? A reduction of CNF boolean satisfiability to the circulation problem in an undirected graph

Consider the CNF formula $a \wedge \neg a$. This has two clauses, $a$, and $\neg a$. If I understand your scheme correctly this maps to the following flow problem: This clearly has a solution (1 flow ...
• 13.6k

### Improvement of algorithm due to constrained graph

Edmonds-Karp algorithm works by building successive flows $f_0, \dots, f_n$ where each flow $f_{i+1}$ can be obtained by combining $f_i$ and a path in the "residual graph" $G_{f_i}$ obtained through a ...
• 153

### New Applications of Network Flow

Network flow has been used for all sorts of interesting and surprising tasks in computer vision and image processing. For instance, it has been used for image segmentation, image stitching, seam ...
• 162k
Accepted

### Perfect matching in a bipartite regular graph in linear time

There is a classical linear time algorithm of Gabow and Kariv. The first step is to find an Eulerian tour. You do this by starting at an arbitrary vertex and following an arbitrary path until you ...
• 278k

### Flow graph that requires pushing back flow in Ford Fulkerson

There is a network that forces Ford-Fulkerson to push flow back. Intuition Consider executing Ford-Fulkerson (FF) on any flow network where allÂ edges capacities are at least 2. No matter how FF ...
• 930