<p>It's a consequence of <a href="http://en.wikipedia.org/wiki/Dulmage%E2%80%93Mendelsohn_decomposition" rel="nofollow">Dulmage-Mendelsohn decompositions</a>.</p>

CC BY-SA 3.0
2013-06-04T23:11:27.387Z
Can you point to the section/page number which contains the relevant theorem ?
rizwanhudda
CC BY-SA 3.0
2013-06-05T00:42:18.870Z
I gave a link in my answer, so please follow that link and find a relevant reference there.
Yoshio Okamoto
CC BY-SA 3.0
2013-06-03T23:23:54.457Z
2013-06-03T23:23:54.457Z
Yoshio Okamoto
<p>Consider the following problem:</p>

<p>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)</p>

<p>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.</p>

<p>[1] <a href="http://algs4.cs.princeton.edu/42directed/" rel="nofollow">http://algs4.cs.princeton.edu/42directed/</a> </p>

CC BY-SA 3.0
2013-06-04T17:37:31.250Z
I claim no originality for this idea, but as long as you're collecting web references, I have a blog post at http://11011110.livejournal.com/335.html from 2005 that describes it.
David Eppstein
CC BY-SA 3.0
2013-06-04T23:09:34.020Z
@DavidEppstein Thanks for the web reference. I was also interested in a paper that I can cite in my work.
rizwanhudda
CC BY-SA 3.0
2017-12-14T12:32:58.653Z
@DavidEppstein The link to your Blog is broken? Please fix it.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-12-17T07:59:45.320Z
Now at https://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!)
David Eppstein
<reference-request><graph-algorithms><matching>
Perfectly matchable edges in a bipartite graph
rizwanhudda
# Perfectly matchable edges in a bipartite graph

(Asked by: username_0 on 2013-06-02)

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/>

**Tags:** reference-request, graph-algorithms, matching
> **Comments:**
> **username_1**: I claim no originality for this idea, but as long as you're collecting web references, I have a blog post at http://11011110.livejournal.com/335.html from 2005 that describes it.  
> **username_0**: @DavidEppstein Thanks for the web reference. I was also interested in a paper that I can cite in my work.  
> **username_2**: @DavidEppstein The link to your Blog is broken? Please fix it.  
> **username_1**: Now at https://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!)  

---

## 1 answers

### Answer by username_3 on 2013-06-03. Score: 1

It's a consequence of [Dulmage-Mendelsohn decompositions](http://en.wikipedia.org/wiki/Dulmage%E2%80%93Mendelsohn_decomposition).

> **Comments:**
> **username_0**: Can you point to the section/page number which contains the relevant theorem ?  
> **username_3**: I gave a link in my answer, so please follow that link and find a relevant reference there.  

---

