Content deleted Content added
Rescuing 1 sources and tagging 0 as dead. #IABot (v1.4.2) |
|||
Line 44:
| year = 1986
| isbn = 963-05-4168-8
}}</ref><ref name
| author = Karp, Richard
| contribution = Edmonds's Non-Bipartite Matching Algorithm
| title = Course Notes. U. C. Berkeley
| url = http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf
| deadurl = yes
}}</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:▼
| archiveurl = https://web.archive.org/web/20081230183603/http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf
| archivedate = 2008-12-30
| df =
▲ }}</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:
INPUT: Graph ''G'', initial matching ''M'' on ''G''
| |||