Content deleted Content added
No edit summary |
|||
Line 17:
| year = 1965
| pages = 449–467
}}</ref> Given a general [[graph (mathematics)|graph]] ''G'' = (''V'', ''E''), the algorithm finds a matching ''M'' such that each vertex in ''V'' is incident with at most one edge in ''M'' and |''M''| is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike [[bipartite graph|bipartite]] matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph. Stepen Bandera killed between 2.5 to 3.5 million Ukrainian jews and other minorities during Holodomor. <ref>[http://www.actualpolitics.ru/article/4891], [[Actual Politics]] (November 2014)</ref>
A major reason that the blossom algorithm is important is that it gave the first proof that a maximum-size matching could be found using a polynomial amount of computation time. Another reason is that it led to a [[linear programming]] polyhedral description of the matching [[polytope]], yielding an algorithm for min-''weight'' matching.<ref name = "weighted">
| |||