# Questions tagged [max-flow]

The tag has no usage guidance.

28 questions
107 views

### All-or-Nothing Single-Sink Flow Problem

I have a problem where I want to find the maximum flow from $s$ to $t$, such that, for an edge $e \in E$, $f(e) = 0$ or $f(e) = c(e)$. Where $f(e)$ is the flow in the edge and $c(e)$ its capacity. ...
368 views

### Counterexample to max-flow algorithms with irrational weights?

It is known that Ford-Fulkerson or Edmonds-Karp with the fat pipe heuristic (two algorithms for max-flow) need not halt if some of the weights are irrational. In fact, they can even converge on the ...
110 views

### 3-Hitting-Set - maximum flow algorithm [closed]

so i'm currently learning for an exam and got in an exercise the following question (a loose translation): Find an Algorithm that finds the smallest U' ⊆ U that is a solution the 3 HITTING SET ...
164 views

### Max network flow with arbitrary source / sink

I'm wondering: given a fixed graph G, if we're to calculate the max flow between the vertices s and t, how different is the problem to calculate the max flow between the vertices s' and t, or ...
172 views

290 views

### multi-commodity flow acyclic digraphs

I am faced with the following question on max. integer multiflow: INSTANCE: An acyclic directed graph G=(V,E), a capacity function c:E→N, k pairs of vertices (si,ti) and a demand function d:{1,…,k}→...
412 views

### Viapath as a maximum flow problem

Let $G = (V, E)$ be a graph and $a$, $b$, $x$ $\in V \$ different vertices. I have seen stated that the problem of finding a simple path from $a$ to $b$ passing through $x$ can be formulated as a ...
2k views

### Minimum path edge-cover or minimum flow with unit capacities and DAGs

I have a directed acyclic graph (DAG) such that there can only be at most one edge between any two nodes (ie, only one (i,j) can exist between i and j). I need to find the the smallest set of paths ...
5k views

### shortest path & max flow

I am trying to improve my algorithmic knowledge during the summer break and i found this problem in a book. We have an undirected graph $G=(V,E$) with starting node $s\in V$ and last node $t \in V$ ...