# Questions tagged [network-flow]

For questions about networks that inhibit source and sink nodes and a notion of flow.

405 questions
Filter by
Sorted by
Tagged with
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-...
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 ...
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
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. ...
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
32 views

• 31
209 views

73 views

• 11
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
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
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
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
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
47 views

• 442
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
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
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
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
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
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
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
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....
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 ...
1 vote
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 ... 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? 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, ...
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
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
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 ...
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
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 ...