ACM Comm 2014 08 Efficient Maximum Flow Algorithms (Notes)

From University
Jump to: navigation, search
"Efficient Maximum Flow Algorithms" CACM August 2014

Efficient Maximum Flow Algorithms
by Andrew V. Goldberg and Robert E. Tarjan, p. 82-89

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

  1. The Maximum Flow Problem[1]
  2. Minimum Cut Problem[2]
  3. Combinatorial Optimization Problems[3]
  4. The maximum flow, minimum cut theorem says the maximum flow value is equal to the minimum cut capacity.
  5. How is the flow limited to the shortest path?
    1. By blocking the flow from splitting along multiple paths or taking a longer path.
    2. Thus, "Blocking Paths" are critical for steering the flow.
  6. Solutions can be the shortest path or the largest volume, or both.
  7. Dynamic Tree Data Structure[4]
  8. Blocking Flow Method
  9. Push-Relabel Method
  10. Binary Blocking Flow Algorithm

References

Internal Links

Parent Article: Reading Notes