Questions tagged [network-flow]
For questions about networks that inhibit source and sink nodes and a notion of flow.
405
questions
2
votes
1
answer
55
views
Scheduling jobs with fixed start and end time on limited machines
The problem: Given n jobs with fixed start and end times, and k machines each capable of doing only one job at a time, find if it is possible to schedule all n jobs on these k machines using network-...
- 33
0
votes
0
answers
19
views
Prove that if the residual graph doesn't contain a path from $u$ to $v$, then $e=(u,v)$ crosses some minimum cut
Prove: given a flow network $N=(G,s,t,c)$ with a maximum flow $f^*$ and a given edge $e=(u,v)$,
then there's no path from $u$ to $v$ in $N_{f^*}$.
I've seen this thread, but the only answer there is ...
- 87
0
votes
1
answer
21
views
Maximum Flow with recursive, dynamic weights
I am looking for an algorithm that functions similarly to the maximum flow algorithm. The only difference is that each edges weight changes according to the weight that it was traversed before, and ...
- 123
1
vote
1
answer
27
views
Do all Wardrop Equilibria have the same social cost?
I'm currently studying non-atomic congestion games, and i've come accross the following definition of the price of anarchy:
Let $f$ be a Wardrop equilibrium and let $f^*$ be a system optimal flow. ...
2
votes
1
answer
62
views
How to configure Minimum Cost Maximum Flow to solve Unbalanced Assignment Problem?
Problem
$n$ objects have to be assigned to $m$ categories, with $n \ge m$. Assigning an object $i \in [n]$ to a category $j \in [m]$ comes with a cost $c_{ij}$. Multiple objects can be mapped to the ...
- 137
0
votes
0
answers
32
views
Proving the sum equivalence of an s-t-flow
Let N = (D = (V, A), u) be a network and s, t ∈ V , s not equal to t
For every s-t-flow for $R^A$ and every pair of s − t-cuts S, S' ⊂ V holds
$\sum _{a∈δ^+(S)}f_a − \sum _{a∈δ^-(S)}f_a = \sum _{a∈δ^+(...
- 101
0
votes
0
answers
44
views
Pushing Boxes, help me solve this graph problem!
Given a directed, acyclic graph with nodes representing boxes/objects at rest and edges that point to neighbouring boxes/objects in direct contact. Each node will be assigned a number that represents ...
0
votes
0
answers
21
views
Understanding specific usage of dinic's algorithm
In a book I have from my aglorithm course, I have the following example:
Given a flow network $N(G(V,E),s,t,c)$, with positive capacities for all edges, find a minimum cut S* with minimum numbers of ...
- 1
1
vote
1
answer
72
views
Characterization of circular flow
We are given a directed graph $G$, capacity $u$, source $s$ and sink $t$. We call a flow from $s$ to $t$ a circular flow if the size of the flow is $0$. We say that function $l: E(G) \to R^{+}_{0}$ is ...
- 515
1
vote
1
answer
90
views
Maximum flow of a graph and minimum capacity of a s-t cut
Question: Find the maximum flow and minimum capacity of a s-t cut of the following graph. The capacity on every edge is 1 . The continuous edges have a flow of 0 and the dotted straight edges have a ...
- 155
2
votes
1
answer
25
views
Find cycles with fixed number of edges without shared vertices in a directed graph
I am trying to find minimum weighted cycles with fixed number of edges without shared vertices in a weighted directed graph. Specifically, say I need to find 4 cycles (one cycle per user) each with 5, ...
- 21
2
votes
1
answer
107
views
Linear Algebra Network Flow Problem. What happens if we allow the street to be a 2 way road.
For this problem, the direction of traffic flow is only in one way. Thus, they say that the constraints for x1,x2,x3,x4 must be greater or equal than 0. I don't understand why having a one way road ...
- 557
0
votes
0
answers
54
views
Initialization of the Network Simplex Method
I am studying Chapter 7 (Network Flow Problems) of the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. On page 286 the authors briefly describe a way to deal with the ...
- 455
0
votes
0
answers
103
views
Uniqueness of minimum cost flow and reduced cost optimality condition
Let $G = (V, E)$ be a directed graph with edge costs $c: E \rightarrow \mathbb{Z}_{\geq 0}$ and edge capacities $w: E \rightarrow \mathbb{Z}_{\geq 0}$. Let $f^*: E \rightarrow \mathbb{R}_{\geq 0}$ be ...
- 311
3
votes
1
answer
45
views
A lemma in the proof of push-relabel maximum flow algorithm.
It is lemma 4.3, I have been thinking about it for 3 days. A detailed description is given below.
In "A new approach to the Maximum-Flow Problem", 1988, by Goldberg, to prove the $\mathcal{O}...
- 31
9
votes
2
answers
209
views
Limit of an integral (coming from random walks and networks) as $n\to\infty$
I have the following integral on hand $$I_n=\int_{0}^\infty\frac1x\left[1-\left(\frac{x-1}{x+1}\right)^n\left(\frac{x-i}{x+i}\right)^{-n}\right]\ \mathrm dx$$
I am trying to find out what $\lim_{n\to\...
- 1,508
2
votes
0
answers
52
views
Maximum number of pairwise vertex-disjoint paths
My problem is:
Let $G$ be a graph, and let $A, B ⊆ V (G)$ (not necessarily disjoint). Prove that the
maximum number of pairwise vertex-disjoint $A$, $B$-paths in $G$ equals the minimum size of a set
$...
- 21
0
votes
0
answers
73
views
Nondegenerate Basic Feasible Solution for network flow problem
I am reading the network simplex algorithm of Bertsimas' Introduction to Linear Optimization. The graph below shows a degenerate basic feasible solution because the flow from node $6$ to node $7$ is $...
1
vote
0
answers
39
views
What does the result of this exercise tell us? ("Introduction to Algorithms 3rd Edition" by CLRS)
I am reading "Introduction to Algorithms 3rd Edition" by CLRS.
The following exercise is Exercise 26.1-3 for section 26.1 "Flow networks".
In section 26.1, the authors give a graph-...
- 7,442
1
vote
1
answer
46
views
Do these sentences in "Algorithms 4th Edition" contain an errata? ("Algorithms 4th Edition" by Robert Sedgewick and Kevin Wayne)
I am reading "Algorithms 4th Edition" by Robert Sedgewick and Kevin Wayne.
I am reading a section about Network-flow algorithms
Recall from SECTION 4.3 that a cut in a graph is a partition ...
- 7,442
0
votes
1
answer
21
views
maximum flow algorithm to find a maximum cardinality matching in a bipartite graph.
How could I show how a maximum flow problem can be used to find a maximum cardinality matching in a bipartite graph?
thanks in advance
- 13
0
votes
1
answer
34
views
Is the Generalized Assignment Problem with weights=1 NP-hard?
Description
The Generalized Assignment Problem consists into assigning an items $i$ to a bins $j$.
If we assign item $i$ to bin $j$ (i.e., $x_{ij}=1$) we obtain a profit $p_{ij}$.
Each bin $i$ has its ...
0
votes
1
answer
72
views
How to maximize a flow in a network without knowing direction of data transferring from a node
Suppose we have a network (shown in the image above), and the maximum transfer rate between two computers is written on each link. We want to maximize the transfer rate from computer $o$ to computer $...
- 11
2
votes
1
answer
28
views
Is a network flow equivalent to a walk?
Consider a directed graph where each edge has infinite capacity.
Now consider a directed walk on this graph from arbirtary node s to arbitrary node t with $s \neq t$.
Definition (Directed walk): A ...
- 21
0
votes
0
answers
19
views
Network Flows - a cut
A really simple question that I cannot find a direct answer to. I guess it's considered so obvious but when finding a cut on a network flow graph (not necessarily min) can it cut an arc twice? TY
- 21
0
votes
1
answer
22
views
Transforming LPP into transportation matrix
I need to transform an LPP into a transportation matrix, however, where I would expect greater than' for constraints on demand, the LPP only has 'less-than' constraints. Any hints on transforming this ...
- 55
1
vote
1
answer
37
views
Comparing network graphs
I started out with a grid graph,
performed some operations on it, and ended up with a set of networks; for example,
,
,
,
I need to compare these graphs.
A thought that I had was to compare them with ...
- 280
0
votes
0
answers
36
views
Comparing networks using graph theory
I'm new to graph theory so forgive if I use unconventional terminology. Please ask if there's any confusion regarding the statements I make.
I have a bunch of undirected, unweighted, simple graphs ...
- 280
1
vote
1
answer
47
views
Best possible way to withdraw amount from different accounts
I need to withdraw the maximum amount from different accounts under the following conditions:
The following are the conditions:
1.) Minimum withdrawal is $\$1$.
2.) Amount can be transferred from one ...
- 19
1
vote
0
answers
45
views
A flow $f$ is maximum $\Leftrightarrow$ $\exists$ an empty $s$-$t$ cut
Given a flow network $(G,\mu,s,t)$. I am thinking about the following statement.
A flow $f$ is maximum $\Leftrightarrow$ $\exists$ an empty $s$-$t$ cut
I know "$\Rightarrow$ is correct, but also &...
- 373
2
votes
0
answers
31
views
Non $0,\pm 1$ integer coefficient polytopes with integral extreme points
Suppose we have a linear system
$$Ax\leq b\quad \text{where}\quad A\in \mathbb{Z}^{m\times n},b\in \mathbb{Z}^m.$$
In integer programming literature, we usually have that $A$ has only $\{0,\pm 1\}$ ...
- 1,211
1
vote
1
answer
40
views
flow+flow is a flow [closed]
I have the following question:
If $f$ is an $s$-$t$ flow in $(G,\mu, s, t)$ and $f'$ is an $s$-$t$ flow in $(G,\mu', s, t)$ then there exists an $s$-$t$ flow in $(G, \mu +\mu', s, t)$ of value $|f|+|f'...
- 442
0
votes
1
answer
73
views
What is the meaning of this math formulation? [closed]
I have been wondering what is the meaning of this sigma with delta negative or plus in there (if my read is correct).
$$
\sum_{i \in \Delta^{-}(j)} x_{i j k}-\sum_{i \in \Delta^{+}(j)} x_{j i k}=0 \...
- 109
0
votes
1
answer
18
views
Max-Flow: Modelling edge dependencies
For a toy problem I'm working on, I'd like to know if its possible to (easily) add the following type of constraints to a max-flow problem: if edge $x_{ij}$ is active (flow > 0), then also $x_{jk}$ ...
- 145
2
votes
0
answers
333
views
Why can matrix rounding be seen as a max flow problem?
For a general max flow problem, we know that each intermediatte node must give away the same amount of flow it receives. Besides this, we also know that the amount of flow that leaves the origin node (...
- 1,171
1
vote
0
answers
12
views
Estimate flux integral of $\frac{1}{|x|}$ in $\Bbb{R}^3$ through a quadratic surface.
My question occured reading this paper in the first example of section 6.
Let $f:\Bbb{R}^3 \rightarrow \Bbb{R}^3$, $f(x)=|x|$ a vector field.
Now divide $\Bbb{R}^3$ up into disjoint unit cubes ...
1
vote
0
answers
103
views
Finding Paths In Tripartite Graphs From Network Flow
Definition (Minimum T-Transversal): Let $T$ be the set of all triangles in a simple graph $G=(V,E)$. A T-transversal is a subset $S\subseteq E(G)$ such that every triangle in $T$ contains at least one ...
- 57
0
votes
0
answers
10
views
Is there any special condition on finding the inital spanning tree for a minimum cost flow problem?
I was wondering...
When we are working with a standard minimun cost flow problem, is there any additional condition on the initial basis besides defining a spanning tree?
Take the graph below as an ...
- 1,171
0
votes
1
answer
20
views
Given a max flow s-t in a network R, provide an algorithm to find the cut of max capacity.
By applying an algorithm we can find the max flow in a network.
Is there a way to find the max capacity cut in O(m) from the residual graph of the max flow?
- 61
1
vote
1
answer
36
views
Bad choice of path in maximum-flow algorithm
I'm currently studying the maximum-flow algorithm and encountered the following problem:
The number on each edge is the capacity. I wonder what kind of bad choice can cause so many iterations. Thanks....
- 702
0
votes
0
answers
16
views
if any valid path has flow value <= gamma, then the maximum flow <= \gamma |E|
Prove this: In a network $(G = (V,E), u, s, t)$ with capacity set $u$, source $s$, and sink $t$, if any path from $s$ to $t$ has its value less than or equal to $\gamma$, then the maximum flow is less ...
- 149
1
vote
0
answers
41
views
Net flow out of $x$ equals net flow into $y$
Let $D=(V, A)$ be a digraph and $f$ a real-valued function on $A$.
I am trying to show:
$\sum\left\{f^{+}(v): v \in V\right\}=\sum\left\{f^{-}(v): v \in V\right\}$,
if $f$ is an $(x, y)$-flow, then ...
user1023562
0
votes
1
answer
52
views
Value of max flow and min cut in a graph with no directed paths
Let $N(x, y)$ be a network which contains no directed $(x, y)$-path.
How do I show that the value of a maximum flow and the capacity of a minimum cut in $N$ are both zero?
user1023562
0
votes
1
answer
26
views
Average of maximal flows and each arc's level of saturation
I am going through the proof of the max-flow min-cut theorem presented in the following paper:
Ford, L., & Fulkerson, D. (1956). Maximal Flow Through a Network. Canadian Journal of Mathematics, 8, ...
2
votes
1
answer
35
views
Maximum flow with minimal number of vertices used
In many of the research problems I encountered recently, the following version of the minimum cost maximum flow problem came up. We are given a directed graph $D$, a source vertex $s$ and a terminal ...
- 33
0
votes
0
answers
21
views
Max/min flow for scheduling slots
So imagine there is a bus schedule:
These are return routes.
NYE<->LND 2 buses needed
NYE<->STN 3 buses needed
STN<->LND 2 buses needed
Single arrow signifies one-way journey. Note ...
- 79
0
votes
0
answers
30
views
Polynomial time "fairness" algorithm that assigns leaders for $m$ tasks amongst $n$ workers.
Suppose we have $n$ workers and $m$ tasks. Suppose each task has a workforce $S_i \subseteq \{1, 2, .., n\}$. Note that $S_i \cap S_j \neq \emptyset$ is possible (and expected).
Given this ...
- 11
0
votes
2
answers
109
views
Sum of weight of edges of each vertex of a $4$ regular graph can be made $0$.
Suppose we have $4$ regular graph $G$. We have to show that each edge can be labelled with $-1$ or $1$ such that the total flow in a vertex is $0$.
There is also a question related to it:
To find an ...
- 12.3k
0
votes
1
answer
144
views
Maximum "k-to-k" matching in bipartite graph
I was "inspired" to extend the concept of Maximum "$2$-to-$1$" matching in a bipartite graph 2-to-1 matching by extending it to "k-to-k" matching for some natural number ...
- 45
1
vote
1
answer
494
views
Maximal flow with multiple sources and sinks
How do I find a maximal flow in a network with multiple sources and sinks using the Ford-Fulkerson algorithm 'without adding anything to the network'. I know that we could add a supersource node and a ...