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
0
votes
1
answer
137
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 ...
- 3
1
vote
1
answer
460
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:
...
- 305
1
vote
1
answer
41
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 ...
- 11
6
votes
2
answers
362
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 ...
D.W.♦
- 156k
0
votes
0
answers
120
views
Prove that there exists a minimum cut (S', T') where S' is the subset of S in which (S, T) is a minimum cut as well
I need to prove the statement $\exists$ a minimum cut $(S', T')$ where $S' \subseteq S$ for any minimum cut $(S, T)$
My attempt: Before proving this statement, I have a lemma if $(S_1, T_1)$ and $(...
- 202
0
votes
0
answers
329
views
Max flow but distribute evenly among candidate vertices
The max-flow algorithm finds the maximum flow through a graph given edge capacities. However, if there is an option between flowing through two edges, it will typically just leverage one of those ...
- 305
5
votes
1
answer
311
views
The same outgoing and incoming degree in graph
I have an undirected graph with $n$ vertices and $m$ edges. How to determinate in $poly (n, m)$, is it possible (and how is it necessary) to orient all the edges so that each vertex has the same ...
- 137
2
votes
0
answers
95
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 ...
- 163
2
votes
1
answer
460
views
Proof of lemma for flow in residual graph
In CLRS 3'rd edition there is a Lemma 26.2 which states that:
Let $G=(V, E)$ be a flow network, let $f$ be a flow in $G,$ and let $p$ be an augmenting path in $G_{f}$. Define a function $f_{p}\colon ...
- 190
1
vote
1
answer
46
views
Looking for an algorithm to minimize cost of edge traversals in a bipartite graph subject to constraints
I have a set of urns that can each hold different amounts of sand. Porters can deliver sand to each urn subject to a transport fee per unit of sand. Each porter has a finite amount of sand they are ...
- 115
0
votes
0
answers
118
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
1
answer
314
views
Determine whether a flow can satisfy node demands in a directed acyclic graph
I have the following problem that I'm unsuccessfully trying to solve:
I have a directed graph with node demands. Unlike circulation with demands, these node demands do not "subtract" from the flow - ...
- 125
1
vote
0
answers
78
views
Partially defined boolean function
Consider a Boolean function $f(x_{1}, x_{2}, \dots, x_{n})$. The value of $f$ is defined on some set of inputs, and some inputs are undefined (let us label undefined value with $?$). It is possible to ...
- 11
2
votes
0
answers
144
views
Add capacity to the uni-weighted graph to increase max flow
Given a uni-weighted graph G (in which each edge has the capacity of 1), and we have k extra capacities (k is an integer) that we can spend on any subset of existing edges. That is, we can increase ...
- 21
1
vote
1
answer
128
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 ...
- 133
1
vote
0
answers
29
views
Maximum edge-disjoint flow
Consider the case where you have two types of flow, let's say "red" flow and "blue" flow. You want to send $k_r$ red flow and $k_b$ blue flow through a DAG $G$ from a source $s$ to a sink $t$ in such ...
- 976
1
vote
2
answers
309
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 ...
- 147
5
votes
1
answer
392
views
Maximum flow on a tripartite graph
I have to solve an assignment problem between $\{1,\dots, N\}$ agents and $\{1,\dots, M\}$ objects, which comes to maximize :
\begin{equation}
\sum_{ij}\beta_{ij}x_{ij}
\end{equation}
where $x_{ij}$ ...
- 51
1
vote
1
answer
609
views
Given a network flow find if there's a min cut that only one of the given edges lay on it
Given a network flow $G=(V,E)$ with capacity function $C$ source $s$ and hole $t$,
and given 2 edges $e_1 , e_2 $.
Find if there exists a min-cut such that only one of the edges belongs to the min-...
- 147
2
votes
0
answers
41
views
FPTAS algorithm to find flow at each link for multi commodity flow problem?
Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the ...
- 23
3
votes
1
answer
184
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. ...
- 131
2
votes
1
answer
658
views
Edmonds-Karp Algorithm with both directed and undirected edges?
How would this work and be implemented?
If you have directed edges pointing away from the source to a bunch of other verticies, and directed edges pointing from those vertices to a sink, but have ...
0
votes
0
answers
47
views
Schedule a Seminar in Minimum Time
There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
- 265
4
votes
1
answer
2k
views
find the union of all min cuts of a flow network
I'm trying to solve the following question :
Given a flow network $N = (G=(V,E),c,s,t)$. Let $\mathcal F$ be the set of all minimum cuts. Prove that $\mathcal F$ is closed under intersections and ...
- 317
1
vote
0
answers
42
views
Getting rid of negative-cost edges in min-cost max-flow algorithmically
I have a min-cost max-flow problem. The designed network (without cycles) gives correct results using cycle cancelling, but it is way too slow. I would like to get rid of negative edges so that I can ...
- 173
0
votes
1
answer
170
views
Network Flow - Minimum flow in a network
I have a directed graph G=(V,E) with a source s$\in V$ and a sink t$\in V$. There is a minimum capacity (lower bound) l $_{e}$ for each edge in G. There are no upper bounds on the edges.
In a course ...
- 115
3
votes
2
answers
886
views
Smallest $s$-component in mincut
Suppose there is a directed graph $G=(V,E)$, with source $s$ and sink $t$, and I compute the max flow on it. Then I know that I can find a min-cut $(A,B)$, by letting $A$ be the set of vertices that ...
- 175
2
votes
1
answer
249
views
Practice question on the applications of flows and cuts
This question is from Erickson's textbook on algorithms, p. 376, question 18.
Faced with the threat of brutally severe budget cuts, Potemkin University
has decided to hire actors to sit in ...
- 121
0
votes
1
answer
539
views
Inviting an optimal subset of persons such that all friends of a person invited are invited
Let's say that you want to invite a person $u$ in party $P$. The
person $u$ will join the party if and only if all the friends of $u$ will join the party as well. Otherwise, $u$ will reject your ...
- 11
2
votes
1
answer
380
views
Proving that max flows of undirected graph and equivalent directed graph are equal
There is an undirected graph $G$. A graph $H$ is constructed by changing each edge $(a,b)$ in $G$ to a pair of directed edges $(a,b)$ and $(b,a)$. How to prove that the maximum flow in $H$ is equal to ...
- 23
0
votes
1
answer
41
views
default TCP Maximum Segment Size
Why default TCP Maximum Segment Size is 536? If found this line in TCP/IP by behrouz forouzan
3
votes
1
answer
5k
views
how to check whether a flow network contains unique maximum flow?
I have been stuck on this problem for few hours, my assignment asks to design an efficient algorithm(polynomial running time) that check whether a given flow network graph contains a unique maximum ...
- 361
1
vote
1
answer
213
views
Intuition behind min cut in a flow network? Whether it's baseball elimination or project selection
I was wondering if someone can give me a general definition of a min-cut besides it being the max flow of a network.
For example, in the baseball elimination problem, if we wanted to find out if ...
- 145
0
votes
1
answer
85
views
Relabel to front, what does topological sort according to admissible network mean?
In the CLRS book it says that "relabel to front" algorithm, which solves the maximum-flow problem, maintains a list of topologically sorted vertices in the admissible network and that vertices with ...
- 172
3
votes
1
answer
534
views
Network flow - minimum flow through edge [duplicate]
In my max flow network, I would like to have an edge with upper bound of the flow (a.k.a. edge capacity) $c_{max}$. However, I would also like to add a lower bound for the flow through the edge, $c_{...
- 173
0
votes
0
answers
19
views
How to divide services and capacities in a graph?
Given a graph where some nodes can provide some services with x,y,z... capacities. A node connected to multiple nodes needs to divide these services to the connected nodes and these nodes themselves ...
- 1
3
votes
1
answer
684
views
Relative vertex capacity in max flow algorithm
I am designing a network for a max flow and would appreciate the following feature:
Say there is a flow incoming to a vertex. I would like to consume some specified amount of that flow and let ...
- 173
1
vote
1
answer
230
views
How to solve the minimum-cost flow problem on a complete graph, with a concave cost function of flow for each edge?
Here is the problem:
Input:
A series of source/sink nodes at fixed positions with given outwards/inwards flow
Edges are NOT specified. The edges can connect any nodes.
The total source and sink ...
- 13
2
votes
0
answers
37
views
Transit scheduling using flow networks
I am studying the maximum/minimum flow question, and was given the following problem:
A traveling agency has $n$ destinations on their service map, and it intends to maintain them with minimum ...
3
votes
1
answer
264
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.
- 31
1
vote
1
answer
59
views
Will a node with no incoming arc or no out coming arc affect the maximum flow?
So in a maximum flow question, say if we have a node which is not $s$ nor $t$, if it has no incoming arc, can we delete it without affecting the maximum flow? What if it has no output arc? How so?
0
votes
0
answers
350
views
Minimum-cut with Maximal number of edges
My question is: in a DAG, each edge has a different value of capacity, we can assume these capacities are integers multiples of the total number of edges. Also, sometimes we can have many minimum cuts,...
9
votes
1
answer
7k
views
Minimum-cut with minimum number of edges
I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph.
Firstly, let'...
- 255
0
votes
1
answer
349
views
Efficient algorithm for assigning weights to nodes in graph to create steady state flow
I'm looking for an efficient algorithm (at least polynomial in the size of the graph, preferably linear) for the following problem:
Definitions:
Given a graph $(V,E)$, with non-negative weights ...
1
vote
1
answer
750
views
Maximum flow with maximum flow on specific edge
I am trying to solve the following problem:
We're given a network flow $(V,E,c,s,t)$ and an edge $(u,v)$. We have to provide an algorithm that computes the maximum flow which has maximum flow on $(u,...
0
votes
0
answers
9
views
What is the average time for a node to transmit on the shared medium for Ethernet? (IEEE 802.3)
Suppose a shared ethernet link L, in which for nodes T1-T4 and a router R are connected:
...
- 167
1
vote
1
answer
80
views
Student Course Allocation Problem with Many Constraints [closed]
Problem statement
In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students.
$i$-th section has:
A student capacity: $cap_i$.
Two lecture timings. (Formally, each ...
- 11
1
vote
1
answer
419
views
Minimum cost max flow network problem with an alternative flow cost
Is there a standard name or a reference for the network flow problem that looks very similar to the minimum cost maximum flow problem, only the flow cost that I wish to minimize isn't sum of edge.flow ...
- 13
4
votes
1
answer
508
views
Min cut of at most k edges
I have been studying for my algorithms exam and whilst doing previous exams found this question for which I am not sure how to handle.
Given a graph $G=(V,E)$ with integer capacities $C:E \rightarrow ...
- 143
0
votes
0
answers
55
views
Proof of lemma from Hong's article about multi-threaded max flow algorithm
I'm struggling to prove Lemma 3 and Lemma 4 from an article about parallel version of push-relabel algorithm: A lock-free multi-threaded algorithm for the maximum flow problem.
Lemma 3. Any trace ...
