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
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 ...
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
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 ...
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 ...
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 ...
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....
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
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'(...
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 ...
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, ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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) = (...
2
votes
1answer
152 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 ...
2
votes
1answer
55 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
vote
1answer
22 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 ...
1
vote
1answer
70 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$ ...
0
votes
1answer
38 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)$ ...
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 ...
1
vote
1answer
33 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? ...
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
1answer
63 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 ...
1
vote
1answer
214 views

Min path cover problem in Cormen et.al. question about notation

In the book on algorithms by Cormen et.al, the problem 26-2 describes how to obtain a min-path cover for a DAG via max-flow. I have a question about the notation. First, let me quote the problem here: ...

1
2 3 4 5
7