MF1: Max Flow Flashcards
1
Q
max number of iterations in Ford-Fulkerson
A
total flow value (c)
2
Q
when can you go against the edge direction?
A
when the back edge is non-empty
3
Q
Ford Fulkerson runtime
A
O(m * c)
4
Q
time to check whether or not f is a max flow?
A
O(n+m)
- Building residual graph takes O(n+m)
- Run DFS on s to see if t reachable
