4
$\begingroup$

Consider the following problem:

Given a bipartite graph $G = (V, E)$, an unmatched edge is one that does not appear in any perfect matching. Design an algorithm to find all unmatched edges. (assume |V| = n and |E| = m)

There is an $O(m + T(m, n))$ algorithm to solve this problem [1, Web exercise 36]. Where $T(m, n)$ is the time complexity of the best algorithm for finding perfect matching in a bipartite graph $G$. I want to get a reference to the research paper/work where the algorithm was proposed, for citation.

[1] http://algs4.cs.princeton.edu/42directed/

$\endgroup$
1
$\begingroup$

It's a consequence of Dulmage-Mendelsohn decompositions.

$\endgroup$
  • $\begingroup$ Can you point to the section/page number which contains the relevant theorem ? $\endgroup$ – rizwanhudda Jun 4 '13 at 23:11
  • $\begingroup$ I gave a link in my answer, so please follow that link and find a relevant reference there. $\endgroup$ – Yoshio Okamoto Jun 5 '13 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.