# Questions tagged [ford-fulkerson]

The tag has no usage guidance.

14 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
363 views

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

Does there exist a flow graph that always requires flow to be pushed back no matter what ordering of augmenting paths is chosen in Ford Fulkerson? Let's assume we use the standard procedure of ...
1k views

### Ford–Fulkerson with irrational numbers

I am trying to understand why Ford–Fulkerson Algorithm for finding maximum flows doesn't work with irrational numbers? I tried to draw several examples but it seems to work.
593 views

### How can we add back edges in Ford - Fulkerson algorithm?

I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent ...
70 views

### Minimum changes to be made to get Max-flow between each pair of vertices in an undirected graph

I was asked the following problem in an interview: Let M be a N X N matrix, such that: ...
20 views

### Creating capacity graph for a list of flights?

I have a list of flights and for each flight, I have information like source, destination, flight capacity, arrival time, departure time. There are only 8 distinct values that are populated in the ...
28 views

### Max flow through a specific edge

What i'v tried doing so far is to find a simple path from s to t containing e as well as some "bottle-neck edge" of maximal value (i.e. a simple path from s to t, containing e, whose minimum ...
22 views

### Maxflow of graph equal to value of flow plus maxflow of residual graph

I'm reviewing max flow min cut for an upcoming exam and one of the proofs relies on the fact that for any flow $f$ on graph $G$ and residual graph $G_f$, \mathrm{maxflow}(G) = \mathrm{val}(f) + \...
25 views

### Polynomial algorithm for determining if min-cut of network is unique?

How can I come up with an algorithm, that's polynomial, to determine if a given min-cut of some network is a unique min-cut or not?
34 views

### MaxFlow Problem MinCut

Yesterday I found a question here, that asked, if the value of the flow across the edges of the MinCut is at capacity. I think the question has been deleted. But I want to confirm that for the edges ...
40 views

### The path with the highest sum of weights

Mr. Katsaros owns a rectangular olive grove divided into 5 rows and 4 columns. He notes down the amount of olives (pounds) possibly obtainable from each of 20 square sections. The picking starts from ...
144 views

### Will the Ford-Fulkerson method return any value if the residual network is ignored?

The normal Ford-Fulkerson method finds augmenting paths (as long as one exists) while including "back-flows", but if those back-flows are ignored, does there exist a flow network for which algorithm ...
191 views

### Running Time of Ford Fulkerson where all edges have equal capacity

My intuition says it would simply be the number of edges leaving s. I'm assuming it's a valid flow network so sum of capacities leaving s is the same as the sum of capacities entering t, so a max flow ...
I want to organize a business lunch with two societies $E_1$ (mine) and $E_2$. Each society is made of four people from the Executive management and 6 of the Financial Management. I want to organize ...