maximal bipartite matching 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:
Start with some (not necessarily maximal) matching .
Find a path that alternates with an edge , followed by an edge , and so on, ending with some edge .
For each edge in the path, add to if or remove from if . Note that this must increase by .
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.
We begin with a matrix with rows and columns containing s, s, and s, where a indicates in edge in the matching and a indicates an edge not in the matching. Number the columns and number the rows .
Start by labeling each column that contains no s with the symbol .
Now we scan the columns. Scan each column that has been labelled but not scanned. Find each in column that is in an unlabelled row; label this row . Mark column as scanned.
Next, we scan the rows. Scan each row that has been labelled but not scanned. Find the first in row . Label the column in which it appears , and mark row as scanned. If there is no in row , 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 s is a maximal matching.
We enter the flip phase when we scan some row that contains no . This row must have some label , and in column , row of the matrix, there must be a ; change this to a .
Now consider column ; it has some label . If is , clear all the labels and mark all rows and columns unscanned, and begin the labeling phase again. Otherwise, change the at column , row to a .
Move on to row and scan this row.
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.
|Title||maximal bipartite matching algorithm|
|Date of creation||2013-03-22 12:40:11|
|Last modified on||2013-03-22 12:40:11|
|Last modified by||mathcam (2727)|