Part VI · Graph Algorithms and Tree-Graph Techniques
39. Network Flow and Minimum Cuts
8 lessons•37 topics•Intermediate / Advanced
8 of 8 lessons published
39.016 animated
Flow network model
- Source/sink
- Capacity
- Conservation
- Residual graph
- Augmenting paths
- Reverse edges
39.024 animated
Max-flow/min-cut theorem
- Cut capacity
- Residual reachability
- Optimality certificate
- Flow-cut equality
39.034 animated
Ford-Fulkerson
- Augmenting-path method
- Integral capacity guarantee
- Path selection
- Complexity caveats
39.042 animated
Edmonds-Karp
- Shortest augmenting BFS
- O(VE²) bound
- Residual updates
39.054 animated
Dinic's algorithm
- Level graph
- Blocking flow
- DFS augmentation
- Complexity
- Unit capacity variations
39.065 animated
Push-relabel overview
- Vertex excess
- Height labels
- Push
- Relabel
- Gap heuristic
39.074 animated
Min-cost flow
- Costed edges
- Residual negative costs
- Potentials
- Successive shortest augmenting path
39.086 animated
Flow modeling
- Edge-disjoint paths
- Vertex splitting
- Assignment
- Resource allocation
- Circulation with demands
- Lower bounds