Maximum matching

Further to Sivan's comments, there is also my MC21 code that is available
from ACM TOMS algorithms (through netlib) as Algorithm 575.  Of course,
many of you may have seen or used the weighted transversal algorithm (that
uses quite different algorithms) of Duff and Koster, called MC64.

Best wishes

Iain

++++++++++++++++++++++++

> 
> 
> On Saturday, Apr 12, 2003, at 05:19 Asia/Jerusalem, John Gilbert wrote:
> >
> > If A has an inverse, then there exists a (row)
> > permutation P such that P*A has nonzero diagonal;
> > you can use the transitive closure of P*A to
> > predict the structure of inv(A) = inv(P*A)*P.
> >
> 
> Probably obvious:
> 
> You find P using a maximum matching algorithm on the
> bipartite graph that represents A (as Edmond suspected). If the
> maximum matching is perfect (all rows are matched), you get P,
> otherwise, no such P exists.
> 
> Alex Pothen has a Fortran 77 code for finding maximum matchings
> in bipartite graphs, which John and I have used.
> 
> Sivan
> 
>