Content deleted Content added
No edit summary |
m →Augmenting paths: Task 16: replaced (1×) / removed (0×) deprecated |dead-url= and |deadurl= with |url-status=; |
||
Line 49:
| title = Course Notes. U. C. Berkeley
| url = http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf
|
| archiveurl = https://web.archive.org/web/20081230183603/http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf
| archivedate = 2008-12-30
}}</ref> Hence, either a matching is maximum, or it can be augmented. Thus, starting from an initial matching, we can compute a maximum matching by augmenting the current matching with augmenting paths as long as we can find them, and return whenever no augmenting paths are left. We can formalize the algorithm as follows:
| |||