ACM Comm 2014 08 Efficient Maximum Flow Algorithms (Notes)
Efficient Maximum Flow Algorithms |
Efficient Maximum Flow Algorithms
"Though maximum flow algorithms have a long history, revolutionary progress is still being made."
Significant research is still being done on network flow problems.
How an algorithm, here a network algorithm, is investigated and refined over time.
People
Ideas
- The Maximum Flow Problem[1]
- Minimum Cut Problem[2]
- Combinatorial Optimization Problems[3]
- The maximum flow, minimum cut theorem says the maximum flow value is equal to the minimum cut capacity.
- How is the flow limited to the shortest path?
- By blocking the flow from splitting along multiple paths or taking a longer path.
- Thus, "Blocking Paths" are critical for steering the flow.
- Solutions can be the shortest path or the largest volume, or both.
- Dynamic Tree Data Structure[4]
- Blocking Flow Method
- Push-Relabel Method
- Binary Blocking Flow Algorithm
References
Internal Links
Parent Article: Reading Notes