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
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
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