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
3
votes
1
answer
272
views
Forcing an edge to be in S-T min-cut
Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e.
So, I tried couple of steps, first, ...
2
votes
1
answer
89
views
Maximum Flow in a Network
Let $N = (V, E)$ be a network in which the capacity of each edge is either $12$ or $18$.
Prove or disprove:
The value of a maximum flow for $N$ can’t be $56$.
I'm trying to figure out how to ...
- 21
2
votes
1
answer
82
views
Current value of flow in a network
Confused about a question regarding flow networks.
Question is: Given the network below, what is the current value of flow in this network?
Does the current flow of a network refer to the maximum ...
- 23
0
votes
0
answers
151
views
What is the most efficient way to solve a workshop scheduling problem?
I am trying to design an algorithm to solve a workshop scheduling problem.
The problem is as follows:
I have to schedule a workshop consisting of a finite number of time slots, and a finite number of ...
- 101
1
vote
0
answers
93
views
Binary flow in max flow problem
is there a way ensure that there only is flow through vertices c and d and not e or through d and e and not c. But not both at the same time. With an simple extension it is possible to put also ...
4
votes
2
answers
390
views
Does real linear programming produce bipartite perfect matching using maxflow reduction?
Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram:
We can formulate max flow as an linear programming problem with integer variables in ...
- 2,881
2
votes
1
answer
11k
views
Ford-Fulkerson vs Edmonds-Karp
I was reading about maximum flow algorithms comparing the efficiency of the different ones. On the Wikipedia Ford-Fulkerson algorithm page, they present the Edmonds-Karp algorithm as the BFS (instead ...
- 1,758
0
votes
2
answers
1k
views
Confused with the proof that Edmonds-Karp always monotically increases the shortest-paths
The proof for the lemma from "Introduction to Algorithms by Cormen et. al." is not clear for me. I can't comprehend a few things. Here is a lemma and its proof. My questions are below.
The notation ...
- 139
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,431
0
votes
0
answers
31
views
Affects of altering a line in "stop and wait" protocol(no noises)
what will happen if we change "to_physical_layer(&s)" to "to_physical_layer(&r)" in the following code(marked in the code where)?
does it make the protocol fail? if so, show a scenario it ...
- 1
1
vote
2
answers
564
views
Why CLRS example on residual networks does not follows its formula?
I am learning algorithms to solve Maximum Flow problem by reading the CLRS book and confused by the following figure:
That is:
A flow in a residual network provides a roadmap for adding flow to ...
- 139
2
votes
0
answers
117
views
Find optimal redistribution in flow graph
I have directed graph (maybe with cycles), and some resources in vertices (let's say gold). I can transfer gold between vertices only in direction of edges. The task is to minimize maximum value of ...
- 121
0
votes
0
answers
36
views
Maximal number of parallel cellular calls with no adjacent cells in a hexagonal setting
Is it possible to find an optimization to the following theoretical case?
Given is a cellular (phone) system with hexagonal cells, where the volume of transmission and the size of the cells are ...
- 1
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
2
votes
1
answer
371
views
optimal flow for index multiple source and destination in directed graph
I am facing the similar problem to max flow in multiple source-destination directed graph (which has a familiar solution of connecting all the sources to one source and the same for the destination, ...
- 141
1
vote
1
answer
3k
views
residual graph and augmenting path in max flow
I thought I understood max flow perfectly until I got to the exam and we got this. I know how to compute a maximum flow by means of the Ford-Fulkerson algorithm, specify the residual network and ...
- 43
0
votes
1
answer
37
views
What does flow denotes in the minimum-cost network?
What is flow in context of minimum-cost network? I know that a minimum cost network is a directed graph G={V,E}, where each edge has a cost and capacity value. The problem is to find best 'path' to ...
- 101
1
vote
1
answer
88
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
1
vote
1
answer
43
views
Why c_f (u, v) = f (v, u) if f (v, u) not in E?
From page8 of the slide, I think $E$ is all the edges in the graph $G$. But why is $c_f (u, v) = f (v, u)$ if $f (v, u)$ is not in $E$? Why do we care about edge that is not in $E$?
- 149
0
votes
0
answers
388
views
Successive shortest path without reduced costs
The successive shortest path algorithm, used to solve the minimum-cost flow problem, can be described as follows :
Successive shortest path (for minimum-cost flow) :
while all flow is not ...
- 737
1
vote
1
answer
1k
views
Maximum flow with constraints
In a flow network, suppose we add constraints of the following type:
The flow entering a vertex $v$ must be at most the flow exiting a vertex $u$.
Is maximum-flow with such constraints still ...
- 5,730
0
votes
1
answer
39
views
transformation between two formulations of the mincost flow problem
According to this slide, the following two formulations of the mincost flow problem are equivalent:
Given directed graph G = (V, E)
Let u denote capacities
Let c denote edge costs.
A flow ...
- 165
3
votes
1
answer
2k
views
Why in Flow network, there is no reversed edges?
I have read that Flow network is a directed graph, with no self loops and there is no reverse edges and non negative capacity.
However in Residual network, we allow the reverse edges so we can cancel(...
- 131
1
vote
1
answer
787
views
A repository for max flow and mincut datasets
I am not 100% sure if this is the right stackexchange to ask. I have a max-flow algorithm and I am also computing the min-cut from that algorithm.
I want to test the correctness and speed of it and ...
- 111
-2
votes
1
answer
2k
views
Please indicate whether each of the following statements is TRUE or FALSE and provide a brief justification
I provided my answers in the "answer your own question" bit.
I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though?
a)...
- 31
0
votes
1
answer
37
views
Do these answers work even when we change the values?
So I know that these are both true, but if I change the values would they still be true? Do these statements hold for any value?
A) Suppose f is a flow of value 50 from s to t in a flow network G. ...
- 31
4
votes
1
answer
742
views
How to calculate the minimum number of groups, by grouping groups with capacity together?
I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem.
If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the ...
1
vote
1
answer
3k
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
1
vote
2
answers
747
views
How to prove that adding incoming edges to source node doesn't alter the max flow
I am given a homework assignment on this question:
Show that if we add any number of incoming arcs, with any capacities, to the source node, the maximum flow value remains unchanged. Similarly, ...
- 11
0
votes
1
answer
84
views
If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?
My problem is mainly from this lecture notes on convex optimization here page4
Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer ...
- 153
-1
votes
1
answer
1k
views
Maxflow problem
I need help with the following practice problem on network flow:
A cohort of $k$ spies resident in a certain country needs escape routes in case of emergency.
They will be travelling using the ...
- 1
0
votes
1
answer
2k
views
The min number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is
In a sliding window ARQ scheme, the transmitter's window size is N and the receiver's window size is M. The minimum number of distinct sequence numbers required to ensure correct operation of the ARQ ...
1
vote
0
answers
23
views
graph trend filtering results from different maxflow algorithm
We have followed the official code of the Graph trend filtering (GTF) https://arxiv.org/abs/1410.7690, and modified the code with Ford Fulkerson Algorithm (FFA) instead of parametric maxflow. The ...
- 11
0
votes
1
answer
276
views
Possible ways to have cross and full edges in a mincut maxflow
I am trying to solve the following problem about maxflow mincut
it seems like my conclusion is incorrect and I am wonder where.
There is no graph just following question.
An edge e can be (x) ...
- 109
5
votes
2
answers
327
views
Minimum cost circulation problem with bounded number of edges
During an article I am writing, I encountered the following problem:
Let $N=(G=(V,E),W,C)$ be a network with a graph $G$, a weight function $W:E\to R$ and an integer capacity function $C:E \to N$.
...
- 377
4
votes
1
answer
97
views
Optimal flow in a network with non-constant edges' weights
I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather ...
- 457
1
vote
1
answer
663
views
Equivalence of minimum cost circulation problem and minimum cost max flow problem
In the following MIT open course, it is claimed that min-cost circulation reduces to min-cost max-flow:
...
The second part of the proof is showing that min-cost circulation
reduces to min-...
- 165
2
votes
1
answer
2k
views
Does minimum cost flow problem work for real valued edge weights/costs?
I'm a bit confused about the definition of the Minimum Cost Flow problem, in terms of the edge cost (or weight) values.
I don't remember a integral requirement on the cost/weight values for the ...
- 165
1
vote
0
answers
94
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
3
votes
1
answer
235
views
Students in classroom problem - Flow in network
I have room, which is opened some days in week, in different hours each day.
I have multiple students, each has time some days in week, in different hours.
Each student have to visit the room ...
- 31
3
votes
0
answers
254
views
Introduction to the Traffic Light Scheduling Problem
I would like to understand the basics of how traffic light scheduling works. Looking through research papers the topics typically revolve around actual highway systems in urban areas, but also ...
- 2,163
4
votes
1
answer
1k
views
Self loops in max flow problem
So, there can be different types of edges in a directed graph while solving the max flow problem. There can be reverse edges, multiple edges and self loops.
What is the significance of self loops in ...
- 481
1
vote
1
answer
100
views
Minimum capacity cut reduction from digraph with two edge weight sets
Given a digraph $G$ and $f, g : E(G) \mapsto \mathbb{R}$, how would you find a cut $(X,\bar{X})$ with $s \in X$ and $t \in \bar{X}$ such that $\sum_{e \in \delta^+(X)}{f(e)} - \sum_{e \in \delta^-(X)}{...
- 13
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
1
vote
1
answer
239
views
Maximum flow in a graph, and conservation of flow
The requirement for the conservation of flow in a flow network is, as I see it in the MIT lectures on Algorithms, that $\sum_{v\in V}f(u,v)=0$ for every $u\not\in \{s,t\}$ where $s,t$ are the source ...
- 315
0
votes
1
answer
93
views
Multi-type max-flow
Suppose you have $m $ sources $s_i$ and $n $ sinks $t_j$, but every source produces a certain type of flow, out of $k $ types, and every sink demands a certain type as well. We would like to know if ...
- 531
2
votes
1
answer
2k
views
Perfect matching in a bipartite regular graph in linear time
Given a $G=(V,E)$ bipartite, undirected, 4-regular graph, I would like to find a perfect matching in linear time.
It is easy to show that there is a perfect matching for the graph, by using flow and ...
- 563
2
votes
0
answers
159
views
long-lived scheduling using max-flow & push/relabel
I'm writing a scheduler of long-lived Processors which execute long-lived Tasks. Processors and Tasks may each come and go over time, at any time (when a Processor departs, its assigned Tasks now ...
1
vote
1
answer
5k
views
What is a reducible flow graph?
What is a reducible flow graph? sorry if this is a stupid question but I'm having trouble finding an answer.
Also multiple equivalent definitions and some motivation would be nice too.
- 83
9
votes
1
answer
15k
views
How to find max flow in a graph after decrementing an edge capacity?
We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the max flow itself is given, so we receive the value of max flow for ...
- 527