Graph Theory37 sections · 1633 units
Open in Course

Quiz: Edmonds-Karp Complexity

Knowledge check

Check Your Understanding

Edmonds-Karp uses BFS to find augmenting paths. Why does BFS guarantee O(VE2)O(VE^2) time instead of the potentially unbounded Ford-Fulkerson?

  1. A.BFS always finds the path with maximum bottleneck capacity
  2. B.BFS finds shortest augmenting paths, and shortest-path distances never decrease, bounding iterations to O(VE)O(VE)
  3. C.BFS visits fewer nodes than DFS in residual graphs
  4. D.BFS prevents cycles in the augmenting path
Start the roadmap to answer the quizzes and solve the challenges