# Questions tagged [ford-fulkerson]

The tag has no usage guidance.

41 questions
Filter by
Sorted by
Tagged with
13 views

### Inverse Weighted Flow Graph using Ford Fulkerson from T to S

As part of a class assignment I am given this problem: Given a Weighted Flow Graph N(G(V,E),s,t,c) and a flow function f. F is the max flow in the network. If s and t are flipped (The graph is now N'(...
30 views

### How to solve min cost perfect matching problems?

I'm trying to design an algorithm for the following generalized assignment problem. We converted the problem to a weighted bipartite graph constituted of two sets $A$ and $B$ where $|A| \ne |B|$. Any ...
52 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 ...
46 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 ...
22 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 ...
54 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 ...
130 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 ...
60 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 ...
29 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 ...
55 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?
172 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 ...
472 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, ...
144 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.
739 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 ...
656 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 ...
68 views

In page 12 of the slide, it states flow across a cut $(S, T)$ is $f(S, T) = \sum_{u\in S} \sum_{v\in T} f(u,v) - \sum_{u\in S} \sum_{v\in T} f(v,u)$. I think the first part $\sum_{u\in S} \sum_{v\in ... 1answer 32 views ### Flow value over edges in Max flow/Min Cut Ford Fulkerson Is it true that if a given edge e is in the min cut of a graph that there exists a max flow of the graph that has e with its full capacity? 1answer 140 views ### Which flow algorithm on a graph is used when the capacity is a rational number? Does ford fulkerson only use whole numbers? I tried to understand this but without success Thank you 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 588 views ### Minimum cost node cut I am interested in solving the following problem: Given an undirected graph whose vertices are weighted, find a subset of vertices of minimal weight whose removal disconnects the graph. Is there ... 0answers 73 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: ... 0answers 35 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 ... 0answers 41 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 ... 0answers 155 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 ... 0answers 335 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 ... 1answer 366 views ### Question on pseudocode for Ford-Fulkerson in Kleinberg-Tardos Text I am looking at the following pseudocode from the Kleinberg-Tardos text "Algorithm Design". ... 1answer 424 views ### Maximum flow properties I was trying to solve problems in max flow algorithms. And I came across this MIT Lecture Quiz. http://people.csail.mit.edu/moitra/docs/6854hw4.pdf solution : http://people.csail.mit.edu/moitra/docs/... 0answers 75 views ### Applying Ford-Fulkerson to settle a business lunch 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 ... 1answer 4k views ### Checking if a given flow is a maximum flow I'm curious as to if there's any way to check (without having to run a 'whole' maximum-flow-algorithm) whether a given flow$f_e$is the maximum flow of the flow graph$G$in$O(|E|)$time complexity. ... 1answer 263 views ### Operation of the Ford–Fulkerson algorithm given an almost maximum flow [closed] I have been assigned the question: Let$G$be a flow network and$f^*$be the maximum flow computed by the Ford-Fulkerson algorithm. Consider a new flow network$G'$constructed by increasing the ... 1answer 4k views ### Algorithm for solving incremental max flow problem I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed ... 1answer 291 views ### Can max-flow with mutually exclusive edges be reduced to standard max-flow problem? I'm working with a flow network like the following: The source s has four edges, each with capacity 1, out to the nodes A, B, C, and D. All of A, B, C, and D have edges to two other nodes, X and Y, ... 1answer 1k views ### Multiple matching in Maximum Flow problem? I'm sorry if this has already been asked before, but I couldn't find any similar questions. The situation is as such: Assume there are x restaurants, each with a capacity q, and y people, each of ... 0answers 2k 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. 1answer 1k views ### Ford-Fulkerson Algorithm not "pushing back" flow I am told that with every flow network, the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges (i.e. never “pushes back” the flow on any of ... 0answers 434 views ### Ford–Fulkerson algorithm. Counterexamples Consider Ford–Fulkerson algorithm (FF). Look to wiki : The following example shows the first steps of Ford–Fulkerson in a flow network with 4 nodes, source A and sink D. This example shows the ... 1answer 2k views ### Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow? I stumbled across this question and answer (source): Question: Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine ... 0answers 659 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 ... 1answer 52 views ### Flow in a network: Conservation of flow definition This might be too easy... But I just don't get it. I've been reading about flow in networks and I stumbled upon this definition in wikipedia: https://en.wikipedia.org/wiki/Flow_network$\sum\limits_{...
According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how ...