LP&CO 2026 Lecture-31: Finding a perfect matching in a bipartite graph using alternating trees
Nishad-Kothari-IIT-Madras · 45:34 · Watch on YouTube
A matching in a bipartite graph is maximum exactly when no alternating path joins two unmatched vertices, and this lecture builds that search as a tree: grow from a free vertex, follow unused edges and matching edges...