# 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.

326 questions
Filter by
Sorted by
Tagged with
1 vote
22 views

### shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true

I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/). Everything in the first part of the proof (The section ...
1 vote
28 views

### Max flow bottleneck approach flow after k iterations

This is a question from a previous exam in Graph theory and algorithms, the correct answer is E but I don't understand why. Given a network flow $(G,c)$ over graph $G(V,E)$. Assume we run Edmonds-...
1 vote
22 views

### Dominators when node not reachable

For the definition of domination [Wikipedia], a node $d$ of a control-flow graph dominates a node $n$ if every path from the entry node to $n$ must go through $d$. If node $n$ is not reachable from ...
46 views

### Solving the maximum flow problem in the real world

Is it possible to solve the maximum flow problem in the real world, ie. using water running through physical pipes? So you would have a tap at the source node, pipes of various diameter (depending on ...
1 vote
45 views

### Finding source-like nodes in a flow notework

Let $G$ be a flow network, where $c(e)$ is the capacity of an edge, and the source is $s$ and sink $t$. Define a node $v$ to be "source-like" if for every min-cut $(S,T)$ of $G$ where $S$ ...
• 293
25 views

### Looking for an algorithm for multi-path funnel analysis

Suppose we have a dataset with each instance: {uid, action, TS}. The funnel algorithm (e.x https://clickhouse.com/docs/en/sql-reference/aggregate-functions/parametric-functions/#windowfunnel) looks at ...
72 views

### Show a reduction of max flow to min cost

Show a reduction of max flow to min cost (not min cost max flow!!)
28 views

### Lucky Ford Fulkerson

I know that Ford Fulkerson might not terminate. But if we assume we know in advance it terminates for some G, and we always pick the "correct" augmenting path, can we upper bound the number ...
• 149
1 vote
11 views

### What are the locally optimal points in an LP formulation of the max flow problem?

I'm taking a grad level algorithms course and we just ended the course talking about linear programming, and we had previously talked about the max flow/min cut problem. Our professor said that the ...
• 111
55 views

### Given a max flow, generate the residual graph

How do you generate a residual graph given the max flow path of a graph? I saw in this this Stack Overflow post. That in order to calculate the min-cut you can run Edmonds-Karp then get the residual ...
• 141
1 vote
27 views

### Proof that using residual network from Ford-Fulkerson will get you min-cut

So I'm following this article and they use the following algorithm to find the min-cut. Algorithm: Run Ford-Fulkerson algorithm and consider the final residual graph. Find the set of vertices that ...
• 141
17 views

### Convert Linear Program to Network Flow

Given the following network flow problem: $$max \sum_{p \in P}x_p$$ $$s.t. \sum_{x_p \in c_e} x_p \leq c_e, \forall e\in E$$ $$x_p \geq0$$ $P$: All paths from a start node $s$ to end node $t$ $E$: Set ...
• 141
1 vote
119 views

• 211
1 vote
99 views

1 vote
22 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 ...
58 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
56 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 ...