maximum cardinality&weight matching

help!!!

anyone know of an algorithm that finds a maximum cardinality, maximum weight matching in a bipartite graph .

the meaning of maximum cardinality, maximum weight matching (or at least the meaining i'm giving to it) is to:
a. find a matching with a miximum number of edges
b. if more than one matching in step a exist - find the set with the maximum weight.

i know an algorithm exists (i've seen a LEDA header file with the function i described above) but i cant even reach a paper on this specific problem, not to speak of a pseudo-code.

thanks for anyone who gives a shot at this one,
Ulaf.

This is an NP problem (I think) so you'll have to try a back-tracking algorithm. Basicallly you'll have to test each combination until you reach a valid one or run out of possibilities.

ie

V1 = {a,b,c}
V2 = {d,e,f}

E = {(a,f,8),(a,e,10),(b,d,4),(b,e,6),(c,d,4)}

Have your app select the node with the smallest number of edges first. (c in this case) Select the largest edge from that node removing the edge and both nodes. Repeat with the node having the next least number of edges.

1 - (c,d,4) V1={a,b} V2 ={e,f}
2 - (c,d,4),(a,e,10) V1={b} V2 ={f}
-- no edge (b,f) so we rollback one
3 - (c,d,4),(b,d,4) V1={a} V2 ={f}
4 - (c,d,4),(b,d,4),(a,e,10) <-Valid Combo

I may be wrong though, I never was very good with algorithms...

Dear ULAF:
I am looking a simple code in c or c++ for doing the Maximum Weight Matching in bipartite graphs.

Did you found a good one?
I would appreciate if you could send me it.
Waiting for a favorable answer, please accept my best regards,
César

This is definitely not an NP problem; it can be solved
in polynomial time.
Check out Ford and Fulkerson's Max Flow algorithm.

An excellent book is "Combinatorial Optimization, Algorithms And Complexity" here is a link to it at amazon.com:

URL

I think it will answer many of your questions.

hi,
i've got a C code for maximum size cardinality matching in C using ford-fulkerson algorithm.if you want that i can give it to you.
if you got the C/C++ code for maximum weight matching in bipartite graph please send that to me also.
thanks