ABSTRACT
Jack Edmonds has been one of the creators of the field of combinatorial optimization and polyhedral combinatorics. His 1965 paper 'Paths, Trees, and Flowers' was one of the first papers to suggest the possibility of establishing a mathematical theory of efficient combinatorial algorithms. In 1961, while attending a summer workshop at the RAND corporation in Santa Monica, California, Jack Edmonds discovered a good algorithm for the Maximum Matching Problem, whose complexity he conservatively pegged at O(n4). That algorithm is described in the paper Paths, Trees, and Flowers. In its title, the words "paths" and "trees" refer to the standard graph-theoretical concepts. The algorithms augmenting paths are found by a "tree search" combined with a sophisticated process of shrinking certain subgraphs called blossoms into single nodes of a reduced graph. Hence the term "flowers".
