Melvin's digital garden

Network Flow

CREATED: 200701021616

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

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

Links to this note