- Explain how to use a solution to the bipartite matching decision
problem to find a maximum bipartite matching of a graph. Hint: First
use a binary search to find the size of the maximum matching, then use
self-reducibility to find the set of edges that attains this value.
- CLR Exercise 36.4-7 (pg. 946).
- CLR Exercise 36.5-2 (pg. 960).
Up: Complexity (23)
Previous: Colorability Complexity for Planar