Jack Edmonds - Research

Research

One of Edmonds' earliest and most notable contributions is the blossom algorithm for constructing maximum matchings on graphs, discovered in 1961, and published in 1965. This was the first polynomial-time algorithm for maximum matching in graphs. Its generalization to weighted graphs was a conceptual breakthrough in the usage of linear programming ideas in combinatorial optimization.

Additional landmark work of Edmonds is in the area of matroids. He found a polyhedral description for all spanning trees of a graph, and more generally for all independent sets of a matroid. Building on this, as a novel application of linear programming to discrete mathematics, he proved the matroid intersection theorem, a very general min-max combinatorial theorem which, in modern terms, showed that the matroid intersection problem lay in both NP and co-NP.

Edmonds is well-known for his theorems on max-weight branching algorithms and packing edge-disjoint branchings and his work with Richard Karp on faster flow algorithms. The Edmonds–Gallai decomposition theorem describes finite graphs from the point of view of matchings. He introduced polymatroids, submodular flows with Richard Giles, and the terms clutter and blocker in the study of hypergraphs. A recurring theme in his work is to seek algorithms whose time complexity is polynomially bounded by their input size and bit-complexity (see the Cobham–Edmonds thesis).