On Apr 2, 2:12 am, "ipsita" <[EMAIL PROTECTED]> wrote:
> Hello !!!
> Give an algorithm for finding the maximum match in general weighted
> graphs, using max incremental weight property. I think we have to
> first find out all the augmenting paths and then select the one having
> maximum incremental weight and proceed. But how to find all the
> augmenting paths? Plz give all the steps for that.
This problem was solved some time in the late 70's. See for example
TARJAN, R. E. 1983. Data Structures and Network Algorithms. Society
for Industrial and Applied Mathematics, Philadelphia. If I recall
correctly, the technique for finding augmenting paths is called
"blossoms."
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
