Questions tagged [ford-fulkerson]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
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'(...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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?
1
vote
2answers
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 ...
2
votes
1answer
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, ...
3
votes
1answer
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.
13
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
68 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
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?
0
votes
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
1
vote
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 ...
2
votes
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 ...
1
vote
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: ...
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
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 ...
0
votes
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 ...
2
votes
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". ...
0
votes
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/...
0
votes
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 ...
3
votes
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. ...
1
vote
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 ...
4
votes
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 ...
1
vote
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, ...
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
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 ...
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
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 ...
1
vote
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_{...
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
3k 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 ...