Questions tagged [network-flow]
Network flows are used to model concepts like traffic or water pipe systems. The basic idea is to move as many units of flow from source to sink nodes via edges with limited capacity.
361
questions
1
vote
1
answer
130
views
Proof that using residual network from Ford-Fulkerson will get you min-cut
So I'm following this article and they use the following algorithm to find the min-cut.
Algorithm:
Run Ford-Fulkerson algorithm and consider the final residual graph.
Find the set of vertices that ...
- 141
1
vote
1
answer
951
views
All nodes reachable from source in residual network of any max flow are included in $S$ for any min-cut $(S,T)$
Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$.
For each edge $e \in E$, we have $c(e) \in \Bbb N$.
Also, we are given a max flow function $f$ on that network.
Let $...
- 11
1
vote
1
answer
58
views
Using Flow graph to find maximum matching
I recently submitted an answer to the following question (homework in algorithms course):
A guy has m shirts, n pants, and p belts. he wants to make the maximum amount of outfits while abiding by ...
- 13
1
vote
0
answers
385
views
Proof that if the residual network of a max flow has cycles then the max flow is not unique
Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$.
For each edge $e \in E$, we have $c(e) \in \Bbb N$.
also, we are given a max flow function $f$ on that network.
Let $...
- 11
1
vote
1
answer
89
views
Finding 2 paths between 2 source-target pairs
Given an undirected graph $G=(V,E)$ and 2 sources $s_1,s_2$ and 2 targets $t_1,t_2$, I am looking to find paths $P_1$ and $P_2$, where $P_i$ is a path from $s_i$ to $t_i$ and $P_1$ and $P_2$ are edge-...
- 494
1
vote
1
answer
276
views
Question about max flow: If all edges have capacity in integers, does a max flow exist where the flow in every edge is in integers?
Let's assume that for every $e\in E$ it holds that $c(e)$ is an integer. Does it mean that there exists a max flow $f$ that for every $e\in E$ it holds that $f(e)$ is an integer? It sounds obvious but ...
- 43
2
votes
1
answer
118
views
Flow with edge-weight restrictions
I am given a graph $G=(V,E)$ undirected and two vertices, the source vertex $s$ and the target vertex $t$. Additionally, each edge comes with a capacity $c(e)$ (non-negative) and a set of weight ...
- 494
1
vote
1
answer
259
views
How to reduce seating families at tables to maximum flow?
Problem:
We have $p$ different families with $1 \leq i \leq p$ members for the $i$-th family. We also have $q$ tables where table $t_j$ has a capacity of $1 \leq j \leq q$. We want no two members of a ...
- 11
2
votes
1
answer
324
views
Minimum number of edges to remove from a graph, so that MST contains a certain edge
Let's suppose we have a weighted and connected graph. We can easily find the minimum spanning tree for this graph. But let's say we want to "force" a certain edge $e$ to be in the MST. For ...
- 153
2
votes
1
answer
87
views
Max-flow from a to c is at least the minimum of max-flow from a to b and max-flow from b to c
Given a directed weighted graph $G = (V, E, w)$, we refer to the max flow when $x$ is the source and $y$ is the sink in the flow network of the graph $G$ as $f_{x,y}$.
I'm searching for a formal proof ...
- 453
2
votes
1
answer
922
views
Proof that if the residual network of a max flow has no cycles then the max flow is unique
Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$.
For each edge $e \in E$, we have $c(e) \in \Bbb N$.
After running Ford-Fulkerson algorithm a flow function $f$ returned ...
0
votes
0
answers
187
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
105
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
643
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
52
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
2
votes
0
answers
314
views
Finding the cut with the minimum number of edges (including reverse ones)
I do not know how to solve the following problem:
Given a directed graph $G$ with a two nodes $s,t \in V(G)$ find a cut $(S,T)$ with $s \in S$ and $t \in T$ such that $(S,T)$ has the minimum number of ...
- 457
1
vote
0
answers
72
views
Maximum money that can be made
Came across the following question. All the answers provided there have used brute force, more or less. My hunch was that it could be solved using dynamic programming or perhaps, network flow ...
- 111
3
votes
0
answers
133
views
Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time
I am stuck with the following exercise:
Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time?
I am not sure that this is possible....
- 457
0
votes
1
answer
1k
views
How are vertex capacities defined in a flow network?
I'm new to network flows and I'm reading this topic from Cormen's Algorithms book (3rd edition) from 26 chapter. I came across this problem from the 26.1 section
Suppose that, in addition to edge ...
- 15
1
vote
0
answers
47
views
Linear programming and network flow
I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, ...
- 81
0
votes
1
answer
112
views
Edmonds-Karp shortest path vs largest bottleneck
Depending on where I look, some places (https://courses.engr.illinois.edu/cs473/sp2009/notes/19-maxflowalgs.pdf) describe EK algorithm as choosing the st path with ...
- 163
0
votes
1
answer
979
views
Which one of the following is NOT a function of transport layer?
A. routing
B. flow-control
C. congestion control
D. All of the above
My guess is flow-control only because routing and congestion is part of the network layer. The network layer is the third later and ...
1
vote
1
answer
75
views
Assigning balls to bins with constraints
Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with ...
- 115
1
vote
2
answers
215
views
Maximum flow in integer flow network
Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of ...
- 11
2
votes
1
answer
116
views
Edmonds-Karp bound doesn't seem to be tight
The proof that the Edmonds-Karp algorithm will require at most $O(|V||E|)$ uses the fact that when an augmenting path has critical edge $(u, v)$, $\delta_f(u)$ strictly increases. Therefore, that ...
3
votes
0
answers
236
views
How to achieve a "balanced" min-cost flow solution
I'm not too familiar with minimum cost flows, so please bear with me. I need to calculate the minimum cost flow for a network that looks like this:
(The numbers in parentheses next to nodes indicate ...
- 153
0
votes
0
answers
46
views
What is a net flow?
I tried to find strict definition in Google and books, but didn't succeed. How it connected with max flow and residual network?
- 131
1
vote
1
answer
26
views
Tiny question on residual networks
Is it true, that the number of edges in residual network is always less than twise the number of edges in the original flow network? My thoughts, that it's false, because in residual network quantity ...
- 131
0
votes
1
answer
102
views
data transfer minimization problem
You have $2$ computers denoted by $C_1$ and $C_2$ and
$n$ missions $M_1,M_2, \dots M_n$.
Doing the $i$-th mission on $C_1$ (resp. $C_2$) costs $a_i$ (resp. $b_i$).
Moreover if you do $M_i$ and $M_j$ ...
0
votes
1
answer
219
views
Decide if the edges of a mixed graph can be directed in order to be an Eulerian Graph
I'm very stuck with this problem. Given $G = (V, E, A)$ a mixed graph where every edge in $E$ is directed and every edge in $A$ is undirected. Thinking as a max-flow problem, decide if it's possible ...
1
vote
1
answer
24
views
Algorithm for shorthest path that contains exactly n edges of weight 2 in 1,2-weighted directed graph
I am trying to find an efficient algorithm for the following problem:
Input:
weighted directed graph G=(V, E) in which all edges are weigthed either 1 or 2
s,t ∈ V
n ∈ N
Output
shortest path from s ...
2
votes
0
answers
121
views
Min Cost Max Flow algorithms for providing multiple solutions
Minimum Cost Maximum Flow algorithms have been known to provide an optimal flow routing for network flow problems in satisfactory runtime. Some of the algorithms for solving a min-cost max-flow ...
- 21
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
2
votes
1
answer
280
views
Minimizing flow on a 2D matrix network
I am currently dealing with a problem that I believe to be a network flow related problem, and I am trying to find some similar solved problems to help me formulate my solution. I want to make it ...
- 21
1
vote
1
answer
3k
views
What happens when we increase or decrease capacities in the minimum flow?
I am confused from these 2 true-false questions on the max flow and am seeking clarity on the basics.
If in a network we increase the capacity of an edge in the minimum cut, the maximum
flow gets ...
- 659
1
vote
1
answer
200
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
2
votes
0
answers
178
views
Assignment Problem with Minimum and Maximum constraints [duplicate]
I have the following problem:
In a school, there are n students and m clubs, with n > m. Each student needs to be assigned a club. The students have preferences, (say top 3 or top 5) of the clubs ...
- 285
0
votes
1
answer
79
views
Finding max flow in a undirected graph
According to this we can do so by replacing every edge in the undirected graph with two edges backwards and forwards with the same capacity. But I'm having a hard time seeing how this prevents ...
- 131
2
votes
0
answers
150
views
The max-min resource assignment problem
I am wondering if there are any results for the following max-min assignment problem:
Given $n$ machines $C = \{C_1, C_2, \dots, n\}$ with the $k$-th machine has power $C_k$. There are $m$ tasks $T = \...
- 21
2
votes
1
answer
419
views
Finding the maximum s-t flow of a graph $G$ in $O(n+m)$ time when $G-t$ is an arborescence
You are given an directed graph $G = (V , E)$ with positive edge capacities, a source vertex $s \in V$, and a target vertex $t \in V \setminus \{s\}$. $G$ is guaranteed to have the following ...
user133359
2
votes
1
answer
246
views
Algorithm for seeing if there exists a min s-t cut (A,B) in a flow network with node u in A and node v in B
We are given a flow network and two nodes $u$ and $v$. We want to create an algorithm that tells us whether or not there is a minimum s-t cut so that $u$ belongs to the same side of the cut as the ...
- 131
0
votes
0
answers
69
views
Average between 2 max flow is a max flow?
I have 2 max-flow function f1,f2 that are different from one another (atleast on a single edge). I know they give each edge a natural even value.
I constrct 2 types of average functions:
A)$ g (e) = (...
- 435
2
votes
1
answer
215
views
Balanced Network max flow review
I would like a review for my algorithm for the following question:
A flow network is a “balanced network” if for every $v∈V- {s,t}$ it holds that $c_in (v)=c_out (v).$
Let G be a balanced network in ...
- 127
2
votes
1
answer
119
views
Properties of Gomory-Hu trees
Given an undirected graph $G=(V,E)$ a Gomory-Hu tree $T$ for $G$ has the following properties:
$T$ has a node for each vertex in the graph G and each edge in the tree corresponds to a minimum cut ...
- 1,625
1
vote
1
answer
27
views
exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow
Given a network flow and there exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow.
I've had this questions with ...
- 211
2
votes
1
answer
294
views
Given an undirected graph, find an orientation such that every vertex has out-degree at least 3
Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3.
I know how to check if a vertex $v$ has at least $k$ ...
- 241
0
votes
1
answer
67
views
why does relabel take O(VE) time total for unit capacity flow networks?
It is well known that for arbitrary flow networks, Goldberg's push-relabel algorithm takes $O(V^2E)$. Part of that comes from $O(V^2E)$ non-saturating pushes. Another part comes from $O(V)$ ...
- 838
1
vote
1
answer
89
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
...
1
vote
1
answer
39
views
What is the duality between path cover and flow?
Let there be a bipartite directed graph $G=(V,E)$.
Let's say we have a path cover of the graph. In some texts it is said that this path cover "induces" a flow on $G$. What does this mean?
...
- 92
2
votes
1
answer
168
views
Ensure a vertex has the highest flow in max-flow algorithm
Let's suppose we have a supplier, sorting facilities, shipping companies and
a target warehouse.
We produce n packages of the product, and each goes to a different sorting facility (so every facility ...
- 21