Questions tagged [ford-fulkerson]
The ford-fulkerson tag has no usage guidance.
53
questions
0
votes
0
answers
29
views
Why in Edmonds Karp or Ford Fulkerson Algorithm the time complexity of BFS or DFS respectively is O(E) rather than O(V+E)?
For these algorithms, the time complexity of BFS and DFS is O(E).
I have gone through many websites and even the algorithm books, but I never got a clear idea of why it is O(E). It just says it's O(E) ...
0
votes
1
answer
58
views
How to find the subsets S and T and the min-cut of this graph?
I get the residual graph by Ford-Fulkerson Algorithm:
I get that the minimum cut can be found by the residual graph, and when traversing this residual network from the source to all reachable nodes, ...
- 3
0
votes
0
answers
60
views
Network flow - properties of a vertex that belong to any minimum cut
while solving some questions about network flow I was wondering about the following statement:
Given a network flow (a graph $G=(V,E)$ with a source $s \in V$ and sink $t \neq s \in V$) > and an ...
- 229
2
votes
1
answer
54
views
Will the Ford-Fulkerson Algorithm always return the same min-cut for any source-sink from one side of the min-cut to the other?
I was playing around with https://visualgo.net/en/maxflow when I realized a pattern:
Take this graph, for example. We notice that the min-cut divides the graph into two sets of nodes: {0, 2, 3, 6} ...
0
votes
1
answer
112
views
Finding the nodes in the source and sink side of a min-cut
We are learning of the Ford-Fulkerson Algorithm for max-flow/min-cut, and I have been wondering of the following question:
How do we exactly find which nodes are on the "sink" side of the ...
-1
votes
1
answer
226
views
Maximum Flow algorithm. How to prove the following statements
Good Evening,
So I am trying to solve this exercise which is a paticular case of maximum flow algorithm. Here the graph must have all even edges and 1 odd edge and it must have a maximum flow that is ...
- 25
0
votes
0
answers
24
views
Maximize flow through a graph, where edges can be added subject to restrictions
I'm doing a course in algorithms and I'm stuck on this problem.
Given a set of vertices on a grid. Every vertex has a coordinate (x,y).
An source and a sink has ...
- 103
1
vote
1
answer
44
views
Can distance from source to any of the vertex decrease during the run of Ford Fulkerson algorithm?
During the run of Ford Fulkerson algorithm if we label each vertex with d(v) where it means the shortest path distance from source to vertex v in residual graph. Is it possible that for some vertex ...
- 13
1
vote
1
answer
1k
views
How to find a crticial edge in a flow network?
The complete question is as follows:
An edge of a flow network is called critical if decreasing the
capacity of this edge results in a decrease in the maximum flow. Give
an efficient algorithm that ...
- 111
1
vote
1
answer
57
views
Max flow bottleneck approach flow after k iterations
This is a question from a previous exam in Graph theory and algorithms, the correct answer is E but I don't understand why.
Given a network flow $(G,c)$ over graph $G(V,E) $.
Assume we run Edmonds-...
- 232
1
vote
1
answer
66
views
Finding source-like nodes in a flow notework
Let $G$ be a flow network, where $c(e)$ is the capacity of an edge, and the source is $s$ and sink $t$. Define a node $v$ to be "source-like" if for every min-cut $(S,T)$ of $G$ where $S$ ...
- 313
0
votes
0
answers
178
views
How to solve a specific dining problem with max flow network?
n people named i are invited to a party. They are a(i) years old.
We want to position them on some tables by obeying the following criteria:
Each guest must sit around a table.
Each table should have ...
- 9
0
votes
1
answer
103
views
How to find the maximum number of square groups in a board
I'm stuck with the following problem:
Given an n*m board, find the maximum number of square groups that can be positioned on the board.
What are square groups?
They contain 4 distinct squares named: ...
- 9
1
vote
1
answer
556
views
find edges such that if decreased by one unit, the max flow decreases as well
We are given a flow network $G = (V,E,c)$, where $c$ is the capacity function as well as a maximum flow $f_m: E\rightarrow \mathbb R$ from $s$ to $t$. The goal is to find edges such that if decreased ...
0
votes
0
answers
50
views
Min cut with smallest number of edges [duplicate]
Cormen's Algorithms 3rd edition Exercise 26.2-13 Page 731:
Suppose that you wish to find, among all minimum cuts in a flow
network G with integral capacities, one that contains the smallest
number of ...
- 15
1
vote
0
answers
61
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 ...
- 111
1
vote
1
answer
126
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 ...
- 111
1
vote
1
answer
86
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
...
3
votes
1
answer
268
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 ...
- 31
0
votes
1
answer
126
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 ...
- 3
2
votes
0
answers
71
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 ...
- 163
0
votes
0
answers
116
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?
1
vote
2
answers
300
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 ...
- 147
2
votes
1
answer
941
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, ...
- 23
3
votes
1
answer
234
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.
- 31
13
votes
2
answers
1k
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 ...
- 4,421
1
vote
1
answer
1k
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 ...
- 13
1
vote
1
answer
84
views
What is a flow through the cut in the Ford-Fulkerson algorithm?
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 ...
- 149
0
votes
1
answer
38
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?
- 27
0
votes
1
answer
298
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
- 27
1
vote
1
answer
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 ...
- 31
2
votes
1
answer
753
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 ...
- 23
1
vote
0
answers
91
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:
...
- 11
0
votes
0
answers
36
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 ...
- 101
0
votes
0
answers
45
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 ...
0
votes
0
answers
162
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 ...
- 141
0
votes
0
answers
479
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 ...
- 101
2
votes
1
answer
388
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".
...
- 323
0
votes
1
answer
512
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/...
- 31
0
votes
0
answers
80
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 ...
3
votes
1
answer
6k
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.
...
- 265
1
vote
1
answer
297
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 ...
- 121
4
votes
1
answer
5k
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 ...
- 65
1
vote
1
answer
409
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, ...
- 113
0
votes
1
answer
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 ...
5
votes
0
answers
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.
- 51
3
votes
1
answer
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 ...
0
votes
0
answers
493
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 ...
5
votes
1
answer
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 ...
- 153
2
votes
0
answers
710
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 ...
- 135