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$
4
  • 2
    $\begingroup$ I claim no originality for this idea, but as long as you're collecting web references, I have a blog post at 11011110.livejournal.com/335.html from 2005 that describes it. $\endgroup$ Jun 4, 2013 at 17:37
  • $\begingroup$ @DavidEppstein Thanks for the web reference. I was also interested in a paper that I can cite in my work. $\endgroup$ Jun 4, 2013 at 23:09
  • $\begingroup$ @DavidEppstein The link to your Blog is broken? Please fix it. $\endgroup$ Dec 14, 2017 at 12:32
  • $\begingroup$ Now at 11011110.github.io/blog/2005/07/20/updated-python-library.html (I moved my blog there last April. This is the first post I made to it at the old location!) $\endgroup$ Dec 17, 2017 at 7:59

1 Answer 1

1
$\begingroup$

It's a consequence of Dulmage-Mendelsohn decompositions.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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