Revision as of 09:06, 4 April 2020 edit A3nm (talk \| contribs) Extended confirmed users, Pending changes reviewers 4,578 edits put the claim about complexity near the top Tag: 2017 wikitext editor ← Previous edit		Revision as of 09:12, 4 April 2020 edit undo A3nm (talk \| contribs) Extended confirmed users, Pending changes reviewers 4,578 edits →Bipartite matching: rewrite, clarify "standard algorithm" Tag: 2017 wikitext editor Next edit →
Line 191: ===Bipartite matching=== ~~The algorithm reduces to the standard algorithm for matching in bipartite graphs<ref name = "karp notes"/> when~~When ''G'' is [[bipartite graph\|bipartite]]~~. As~~, there are no odd cycles in ''G''. inIn that case, blossoms will never be found and one can simply remove lines B20 – B24 of the algorithm. The algorithm thus reduces to the standard algorithm to construct maximum cardinality matchings in bipartite graphs<ref name = "karp notes"/> where we repeatedly search for an augmenting path by a simple graph traversal: this is for instance the case of the [[Ford–Fulkerson algorithm]]. ===Weighted matching===

Blossom algorithm: Difference between revisions