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.

Filter by
Sorted by
Tagged with
1
vote
1answer
153 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) ...
2
votes
1answer
88 views

Max flow algorithm for floating-point weights and E~=10*V

Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e. ...
2
votes
1answer
31 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 ...
1
vote
1answer
18 views

Reducing a seating problem 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 ...
-1
votes
0answers
52 views

Maximum flow: Dining problem

I have a network flow problem: There are $n$ people invited to a party, the age of person $i$ is $a_i$ years, the waiter must position them in a way such that: Everyone sits around a table There are ...
2
votes
1answer
58 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 ...
2
votes
1answer
62 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
0answers
61 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 ...
0
votes
1answer
60 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: ...
1
vote
1answer
65 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 ...
1
vote
1answer
60 views

Covering maximal number of sets using fixed number of elements

I've encountered some problem which seems general enough to have already been solved. There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$. For ...
1
vote
1answer
81 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 ...
1
vote
1answer
67 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 ...
0
votes
0answers
12 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 ...
2
votes
0answers
48 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 ...
3
votes
0answers
71 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....
1
vote
0answers
63 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 ...
0
votes
1answer
40 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 ...
0
votes
0answers
44 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 ...
0
votes
0answers
14 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'(...
1
vote
1answer
49 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 ...
13
votes
2answers
763 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 ...
9
votes
2answers
817 views

CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proof

In Cormen et. al., Introduction to Algorithms (3rd ed.), I don't get a line in the proof of Lemma 26.1 which states that the augmented flow $f\uparrow f'$ is a flow in $G$ and is s.t. $|f\uparrow f'| ...
1
vote
0answers
28 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, ...
6
votes
2answers
182 views

Integral solutions to circulation problem

Suppose we have a circulation problem (with only one commodity), where all lower bounds, upper bounds, and costs are integers. Are we guaranteed that if there is a solution, then there is an integral ...
1
vote
1answer
27 views

Citation for finding node disjoint paths using maximum flow

We can find the maximum number of vertex disjoint paths in a directed graph using maximum flow algorithm keeping the node capacity and edge capacity to one. I could not find the reference paper for ...
0
votes
1answer
21 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 ...
0
votes
1answer
20 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
1answer
34 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 ...
2
votes
1answer
45 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
0answers
42 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 ...
0
votes
0answers
26 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?
1
vote
1answer
19 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 ...
0
votes
0answers
14 views

Min-cut Max-flow problem: not obvious min-cut

I'm trying to find max-flow of such flow network: It seems to be 5, but how to prove it using the min-cut? I can't see any min-cut, which have a value of 5. I also heard in one video, that in min-cut ...
0
votes
1answer
99 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$ ...
1
vote
1answer
48 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
1answer
44 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
1answer
20 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
0answers
45 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 ...
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 ...
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 ...
2
votes
1answer
137 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 ...
1
vote
1answer
321 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 ...
2
votes
0answers
66 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 ...
0
votes
1answer
33 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 ...
2
votes
0answers
140 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 = \...
2
votes
1answer
197 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 ...
0
votes
0answers
25 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 ...
9
votes
1answer
9k 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 ...
0
votes
0answers
41 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) = (...

1
2 3 4 5
7