# Perfectly matchable edges in a bipartite graph

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.

• 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. Jun 4 '13 at 17:37
• @DavidEppstein Thanks for the web reference. I was also interested in a paper that I can cite in my work. Jun 4 '13 at 23:09
• @DavidEppstein The link to your Blog is broken? Please fix it. Dec 14 '17 at 12:32
• 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!) Dec 17 '17 at 7:59