# Questions tagged [ford-fulkerson]

The tag has no usage guidance.

39 questions
Filter by
Sorted by
Tagged with
2answers
2k views

### Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...
0answers
50 views

### How to find all minimum cuts in network flow [duplicate]

In a network flow graph, using the Ford–Fulkerson algorithm, we can find a residual graph G_f which no augmenting paths. This gives us a way of finding one minimum ...
0answers
26 views

### Multi Source/Sink Max Flow Alternative Reduction

When solving a multi source/sink max flow problem, the classic reduction to the single source/sink problem is to add a new source and sink node with infinite capacities that connect to/from the ...
2answers
634 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 ...
0answers
11 views

### best way to solve max-flow min-cut on paper

I am looking at 7.10 from the Algorithms textbook known as DPV (Dasgupta,C. H.Papadimitriou,and U. V. Vazirani) The graph has vertices s,t and A through F with 10 edges. What is the best way to find ...
1answer
94 views

### How to apply the Ford Fulkerson algorithm to the assignment problem

I am quite familiar with Ford-Fulkerson algorithm but I am having a trouble to apply the algorithm to the following problem. Can someone please give me some hints or better instructions how to use FF ...
1answer
41 views

### Flow graph with non zero lower bound or 0 capacity

I am afraid the question title might not be sufficiently accurate but I could not come up with something more accurate Here is the problem Given 'n' machines Each machine has a set of capabilities ...
1answer
41 views

### Minimum cost flow and Ford-Fulkerson

I have a question concerning the use of the Ford-Fulkerson algorithm. Since a minimum cost flow problem is a linear programming problem, it has a dual problem. That dual would be to maximize a certain ...
0answers
20 views

### Find a maximum flow that also maximizes the flow over a specific edge

Let $G=(V,E,c,s,t)$ be a flow-network, where $s$ is the source, $t$ is the target, and $c:E\mapsto [0,\infty)$ defines the capacity of every edge in the network. Let $e=(u,v)$ be an edge in the ...
0answers
46 views

### Why does the Ford-Fulkerson Maximum flow algorithm not work for irrational capacities?

Can anyone help me understand why the Ford-Fulkerson algorithm does not work in the case of irrational capacities?
2answers
136 views

### Find max flow in a network with all capcities of $\sqrt 2$ and one with 2

Given a graph $G(V, E)$ with capacities on the edges such that all edges have a capacity of $\sqrt2$ apart from one edge with a capacity of 2. need to find max flow efficiently. I can run Dinic on ...
1answer
368 views

### Ford-Fulkerson pseudo-polynomial

Can somebody explain please why Ford-Fulkerson Algorithm has pseudo-polynomial complexity? I understand that the complexity in this case strongly depends on the capacities of the edges of the network, ...
1answer
2k 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 ...
1answer
120 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.
1answer
513 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 ...
1answer
65 views