# Questions tagged [ford-fulkerson]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
18 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?
70 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 ...
92 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, ...
22 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 ...
78 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.
479 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 ...
261 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 ...
51 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 31 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 55 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 1k 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 274 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 71 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 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 ... 0answers 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 ... 0answers 149 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 258 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 328 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 327 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 73 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 3k 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 219 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 3k 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 229 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 909 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 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. 1answer 896 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 383 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 1k 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 623 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 49 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 ...