Blossom algorithm: Difference between revisions

Revision as of 17:41, 30 March 2020

Revision as of 09:06, 4 April 2020

Line 18:

| pages = 449–467

}}</ref> Given a general [[Graph (discrete 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.

The algorithm runs in time <math>O( |E||V|^2)</math>, where <math>|E|</math> is the number of [[edge (graph)|edges]] of the graph and <math>|V|</math> is its number of [[vertex (graph)|vertices]]. A better running time of <math>O( |E| |V|^{1 / 2} )</math> for the same task can be achieved with the much more complex algorithm of Micali and Vazirani<ref name = "micali">{{cite conference

| author1 = Micali, Silvio

| author2 = Vazirani, Vijay

| title = An O(V^1/2E) algorithm for finding maximum matching in general graphs

| conference = 21st Annual Symposium on Foundations of Computer Science

| year = 1980

| publisher = IEEE Computer Society Press, New York

| pages = 17&ndash;27

}}</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">

Line 177 ⟶ 187:

** every exposed vertex in ''G'' is a root of an alternating tree in ''F''.

Each iteration of the loop starting at line B09 either adds to a tree ''T'' in ''F'' (line B10) or finds an augmenting path (line B17) or finds a blossom (line B20). It is easy to see that the running time is <math>O( |E||V|^2)</math>. Micali and Vazirani<ref name = "micali">{{cite conference

| author1 = Micali, Silvio

| author2 = Vazirani, Vijay

| title = An O(V^1/2E) algorithm for finding maximum matching in general graphs

| conference = 21st Annual Symposium on Foundations of Computer Science

| year = 1980

| publisher = IEEE Computer Society Press, New York

| pages = 17&ndash;27

}}</ref> show an algorithm that constructs maximum matching in <math>O( |E| |V|^{1 / 2} )</math> time.

===Bipartite matching===