Lesson plan
Blossom algorithm
In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph , the algorithm finds a matching such that each vertex in is incident with at most one edge in and is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike 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 , where is the number of edges of the graph and is its number of vertices. A better running time of O( |E| \sqrt{ |V| } ) for the same task can be achieved with the more complicated algorithm of Micali and Vazirani. 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.…
Article summary
In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph , the algorithm finds a matching such that each vertex in is incident with at most one edge in and is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike 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 , where is the number of edges of the graph and is its number of vertices. A better running time of O( |E| \sqrt{ |V| } ) for the same task can be achieved with the more complicated algorithm of Micali and Vazirani. 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.…
Key claims
- publication date: 1965 — source: Wikipedia · confidence 0.95
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- The record states that the publication date is "1965". What evidence would count against this claim?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
- Wikipedia https://en.wikipedia.org/w/index.php?oldid=1356000132
Key claims and bibliography are generated from the same tracked claims and sources as the article page.