Questions tagged [ford-fulkerson]

The tag has no usage guidance.

0
votes
0answers
18 views

Maxflow of graph equal to value of flow plus maxflow of residual graph

I'm reviewing max flow min cut for an upcoming exam and one of the proofs relies on the fact that for any flow $f$ on graph $G$ and residual graph $G_f$, $$\mathrm{maxflow}(G) = \mathrm{val}(f) + \...
0
votes
0answers
16 views

Polynomial algorithm for determining if min-cut of network is unique?

How can I come up with an algorithm, that's polynomial, to determine if a given min-cut of some network is a unique min-cut or not?
12
votes
0answers
210 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
45 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
39 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
25 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
23 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
440 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
71 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
68 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
31 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
39 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
113 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
170 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
255 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
262 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
69 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 ...
1
vote
1answer
2k 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
169 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 ...
2
votes
1answer
2k 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
165 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
636 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 ...
2
votes
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.
3
votes
1answer
663 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
317 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 ...
4
votes
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 ...
2
votes
0answers
532 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
43 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
729 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
1answer
1k 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 ...