Blossom algorithm: Difference between revisions

Revision as of 08:31, 7 June 2012

Revision as of 05:22, 21 June 2012

Line 1:

'''The blossom algorithm''' is an [[algorithm]] in [[graph theory]] for constructing [[maximum matching]]s on graphs. The algorithm was discovered by [[Jack Edmonds]] in 1961<ref name = "glimpse">{{Citation

'''Edmonds's matching algorithm'''

| last = Edmonds

<ref name = "algorithm">

| first = Jack

| contribution = A glimpse of heaven

| year = 1991

| title = History of Mathematical Programming --- A Collection of Personal Reminiscences

| editor = J.K. Lenstra, A.H.G. Rinnooy Kan, A. Schrijver, ed.

| pages = 32-54

| publisher = CWI, Amsterdam and North-Holland,

Amsterdam }}</ref>, and published in 1965<ref name = "algorithm">

{{cite journal

| doi = 10.4153/CJM-1965-045-4

Line 9 ⟶ 17:

| year = 1965

| pages = 449&ndash;467

is an [[algorithm]] in [[graph theory]] for constructing [[maximum matching]]s on graphs. The algorithm was discovered by [[Jack Edmonds]] in 1965}}</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. ToUnlike search[[bipartite]] formatching, augmentingthe paths,key somenew idea is that an odd-length cyclescycle in the graph (blossoms) areis contracted to a single verticesvertiex, andwith the search continuescontinuing recursivelyiteratively in the contracted graphsgraph.

}}</ref>

is an [[algorithm]] in [[graph theory]] for constructing [[maximum matching]]s on graphs. The algorithm was discovered by [[Jack Edmonds]] in 1965. 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. To search for augmenting paths, some odd-length cycles in the graph (blossoms) are contracted to single vertices and the search continues recursively in the contracted graphs.

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

{{cite journal

| author = Edmonds, Jack

| title = Maximum matching and a polyhedron with 0,1-vertices

| journal = Journal of Research National Bureau of Standards Section B

| volume = 69

| year = 1965

| pages = 125&ndash;130

}}</ref>.

As elaborated by [[Alexander Schrijver]], further significance of the result comes from the fact that this was the first polytope whose proof of integrality

<blockquote>

does not simply follow just from [[total unimodularity]],

and its description was a breakthrough in polyhedral combinatorics.<ref name="schrijver">{{cite book|first=Alexander|last=Schrijver|authorlink=Alexander Schrijver|title=Combinatorial Optimization: Polyhedra and Efficiency|publisher=Springer|series=Algorithms and Combinatorics|volume=24}}</ref>

</blockquote>

==Augmenting paths==