Questions tagged [ford-fulkerson]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
32 views

How to find all minimum cuts in network flow

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 ...
1
vote
0answers
22 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 ...
0
votes
0answers
10 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 ...
1
vote
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 ...
2
votes
1answer
86 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 ...
0
votes
1answer
37 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 ...
2
votes
0answers
19 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 ...
0
votes
0answers
45 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
2answers
130 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 ...
2
votes
1answer
351 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, ...
3
votes
1answer
113 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.
13
votes
2answers
622 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 ...
1
vote
1answer
497 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 ...
1
vote
1answer
64 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 ...
0
votes
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?
0
votes
1answer
107 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
1
vote
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 ...
2
votes
1answer
420 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 ...
1
vote
0answers
72 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: ...
0
votes
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 ...
0
votes
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 ...
0
votes
0answers
154 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 ...
0
votes
0answers
299 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 ...
2
votes
1answer
353 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". ...
0
votes
1answer
401 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/...
0
votes
0answers
74 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
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. ...
1
vote
1answer
252 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 ...
4
votes
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 ...
1
vote
1answer
267 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, ...
0
votes
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 ...
5
votes
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.
3
votes
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 ...
0
votes
0answers
425 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
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 ...
2
votes
0answers
649 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 ...
1
vote
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_{...
3
votes
5answers
1k views

Why is this flow a max flow?

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 ...
6
votes
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 ...