A new approach to maximum matching in general graphs
本文檔由 technic123 分享于2011-11-26 15:10
We reduce the problem of finding an augmenting path in a general graph to a reachability problem and showthat a slight modification of depth-first search leads to an algorithm for finding such paths. As a consequence,we obtain a straightforward algorithm for maximum matching in general graphs of time complexity O(n^(1/2)*m),where n is the number of nodes and m is th..