MF1: Max Flow Flashcards by Phillip Son

Q

max number of iterations in Ford-Fulkerson

A

total flow value (c)

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

when can you go against the edge direction?

A

when the back edge is non-empty

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Ford Fulkerson runtime

A

O(m * c)

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

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

How well did you know this?

1

Not at all

2

3

4

5

Perfectly