Suggest a Book

# Finding perfect matching in bipartite graphs

Level: unknown

posted Aug 12 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

Let $G = (A,B)$ be a bipartite graph. Hall's theorem implies that $G$ has a perfect matching if and only if $|A| = |B|$ and for each $X \subseteq A$, $|X| \leq |\Gamma(X)|$, where $\Gamma(X)$ is the neighborhood of $X$ in $B$.

• Design a polynomial-time algorithm that either finds a perfect matching in $G$ or a set $X$ violating the above condition.
Source: folklore
delete retag edit

## Stats

Posted: Aug 12 '12

Seen: 70 times

Last updated: Aug 13 '12