# Network Flow

CREATED: 200701021616

Ahuja et al, Network Flow: Theory, Algorithms and Applications

https://www.networkflowalgs.com/

maximum flow/minimum cut

- augmenting path on residual graph
- fewest edges path
- highest capacity path

- Dinic’s algorithm
- layered graph and blocking flow

- pushâ€“relabel algorithm
- does only local operations on vertices with positive excess

minimum cost max flow

- cycle-cancelling
- sucessive shortest path

generalized maximum flow

- gain function on each edge
- Onaga’s algorithm
- cancel all flow generating cycles
- use the highest gain path to largest flow within capacity constrints to sink
- this does not create flow generating cycles

minimum cost generalized maximum flow

- equivalent to linear programming where every column of the constraint matrix has at most 2 non-zero entries
- no strongly polynomial time algorithm for this case

- every LP can be transformed to one with at most 3 non-zero entries per column