PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
maximal bipartite matching algorithm (Algorithm)

The maximal bipartite matching algorithm is similar some ways to the Ford-Fulkerson algorithm for network flow. This is not a coincidence; network flows and matchings are closely related. This algorithm, however, avoids some of the overhead associated with finding network flow.

The basic idea behind this algorithm is as follows:

  1. Start with some (not necessarily maximal) matching $ M$.
  2. Find a path that alternates with an edge $ e_1 \not\in M$, followed by an edge $ e_2 \in M$, and so on, ending with some edge $ e_f \not\in M$.
  3. For each edge $ e$ in the path, add $ e$ to $ M$ if $ e \not\in M$ or remove $ e$ from $ M$ if $ e \in M$. Note that this must increase $ \vert M\vert$ by $ 1$.
  4. Repeat until we can no longer augment the matching in this manner.

The algorithm employs a clever labeling trick to find these paths and to ensure that the set of edges chosen remains a valid matching.

The algorithm as described here uses the matrix form of a bipartite graph. Translating the matching from a matrix to a graph is straightforward.

There are two phases to this algorithm: labeling and flipping.

Labeling

We begin with a matrix with $ R$ rows and $ C$ columns containing 0s, $ 1$s, and $ 1*$s, where a $ 1*$ indicates in edge in the matching and a $ 1$ indicates an edge not in the matching. Number the columns $ 1 \dots C$ and number the rows $ 1 \dots R$.

Start by labeling each column that contains no $ 1*$s with the symbol $ \char93 $.

Now we scan the columns. Scan each column $ i$ that has been labelled but not scanned. Find each $ 1$ in column $ i$ that is in an unlabelled row; label this row $ i$. Mark column $ i$ as scanned.

Next, we scan the rows. Scan each row $ j$ that has been labelled but not scanned. Find the first $ 1*$ in row $ j$. Label the column in which it appears $ j$, and mark row $ j$ as scanned. If there is no $ 1*$ in row $ j$, proceed to the flipping phase.

Otherwise, go back to column scanning. Continue scanning and labelling until there are no labelled, unscanned rows or columns; at that point, the set of $ 1*$s is a maximal matching.

Flipping

We enter the flip phase when we scan some row $ j$ that contains no $ 1*$. This row must have some label $ c$, and in column $ c$, row $ j$ of the matrix, there must be a $ 1$; change this to a $ 1*$.

Now consider column $ c$; it has some label $ r$. If $ r$ is $ \char93 $, clear all the labels and mark all rows and columns unscanned, and begin the labeling phase again. Otherwise, change the $ 1*$ at column $ c$, row $ r$ to a $ 1$.

Move on to row $ r$ and scan this row.

Notes

The algorithm must begin with some matching; we may begin with the empty set (or a single edge), since that is always a matching. However, each iteration through the process increases the size of the matching by exactly one. Therefore, we can make a simple optimization by starting with a larger matching. A naïve greedy algorithm can quickly choose a valid matching that is usually close to the size of the maximal matching; we may initalize our matrix with that matching to give the procedure a head start.



"maximal bipartite matching algorithm" is owned by mathcam. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

Log in to rate this entry.
(view current ratings)

Cross-references: simple, size, iteration, empty set, clear, maximal matching, point, labelling, label, contains, number, columns, rows, graph, bipartite graph, matrix, labeling, edge, path, matchings, network flow, algorithm, similar
There is 1 reference to this entry.

This is version 4 of maximal bipartite matching algorithm, born on 2002-05-26, modified 2005-05-15.
Object id is 2943, canonical name is MaximalBipartiteMatchingAlgorithm.
Accessed 16083 times total.

Classification:
AMS MSC: 05C70 (Combinatorics :: Graph theory :: Factorization, matching, covering and packing)
Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy
Errors in description by efagerho on 2006-04-11 08:41:37
I was googling after the description of this algorithm (I've seen it before in some algorithm course, but didn't remember where) and stumbled upon this.

Anyway trying to implement it I noticed that it has quite a few inaccuracies almost to the point where the whole description is more or less useless. This is what first comes up:

In "labeling":
"Find each 1 in column i that is in an unlabelled row; label this row i. Mark column i as scanned."

Clearly if the we start with an empty matching where all rows are labeled "#", then no rows are going to be relabeled. In this situation we are going to proceed to flipping immediately for row 1. This contradicts what is written in the definition, because now our c is going to be "#".

Understanding the text in another way, we could look at the following sentence in "labeling":

"Scan each row j that has been labelled but not scanned."

Here "that has been labelled" could be understood to be the rows that had their label changed during the previous scan of columns or to simply mean all labelled rows. I would assume that the meaning is the latter. However, the latter case leads to the undefined behaviour in "flipping" i just described while the former leads to a dead end in "labelling", because flipping is never reached and thus no edge is ever going to be marked 1*.

I hope someone could elaborate on the details. I'm still not sure if I'm going to implement maximal matching in exactly this way or use my existing implementation of Ford-Fulkerson (which is overkill for edges with binary capacities), but if I do, I'll post some suggestions.
[ reply | up ]
maximal bipartite matching: confused by an example by chen666 on 2005-05-01 18:02:48
Hi. I am trying to use maximum bipartite matching on my (bioinformatics) research. I have some basic knowledge on discrete math, but got a little confused when trying to understand this algorithm. I got a simple example for which this algorithm doesn't produce desired result. It's likely I misunderstood some concepts, and would appreciate if you could point out my mistake. The example is:

Bipartite graph G(X,Y,E), where X={A, B, C}, Y={D, E, F, G}, E={AD, AE, BD, BE, BF, BG, CF, CG}. To follow the steps in the algorithm, assume the initial matching M={AE}:
1) M={AE};
2) M-augumenting path D->B = {DA, AE, EB};
3) M={DA, EB};
4) Got stuck here. I couldn't find an M-augumenting path. But obviously this is not the solution.

Thanks. -- JC
[ reply | up ]
maximal bipartite matching algorithm by jjmvf6 on 2005-03-02 23:05:47
I have been trying to use the maximal bipartite matching algorithm. I have been able to create several graphs were the algorithm does not find the maximal matching. Maybe I am not fully understanding how to implement it. Is there any more information available?
[ reply | up ]
Interact
post | correct | update request | add example | add (any)