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