Graph Theory37 sections · 1633 units
Open in Course

Quiz: Kuhn's Algorithm Complexity

Knowledge check

Check Your Understanding

In Kuhn's algorithm, you run DFS from each unmatched left node to find augmenting paths. For a bipartite graph with nn left nodes and mm edges, what is the time complexity?

  1. A.O(n×m)O(n \times m)
  2. B.O(n+m)O(n + m)
  3. C.O(n2×m)O(n^2 \times m)
  4. D.O(mlogn)O(m \log n)
Start the roadmap to answer the quizzes and solve the challenges