8.1 Why the Ford-Fulkerson algorithm looks so familiar Flashcards

1
Q

How does a biparite matching reduce to a flow network

A
  • Include source and sink
  • Direct edges, weight 1
  • Augmenting path => matched and non matching since backward edge
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How to simulate rational weights in a flow network

A

Multiply each weight by k : all integers

Note: Runtime is prop to F*(v) so prime numbers can mess up runtime

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Edmonds-Karp: when to use it, what is its runtime and how its different to FF (flow networks)

A
  • When we have irrational edge capacities (potentially bad numbers) - FF won’t terminate
  • O(|V||E|^2) => in practice worse than FF
  • Use BFS rather than DFS
How well did you know this?
1
Not at all
2
3
4
5
Perfectly