# Questions tagged [ford-fulkerson]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
771 views

### Given max-flow determine if edge is in a min-cut

We were given an exam question of: Given a flow network G=(V,E) with integer edge capacities, a max-flow f in G, and a specific edge e in E, design a linear time algorithm that determines whether or ...
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 ...
343 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 ...
62 views

### is it possible to find the maximal min cut in polynomial time?

A maximal minimum cut is a minimum capacity cut with the largest number of edges.
27 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?
173 views

### Min-cut in a network with zero flow from source to sink

The max-flow min-cut theorem guarantees that the min-cut of a directed network equals the maximum flow. And we can compute $S$ and $T$, are disjoint subsets containing source node and sink node ...