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).
Read more about this topic: Jack Edmonds
Famous quotes containing the word research:
“The working woman may be quick to see any problems with children as her fault because she isn’t as available to them. However, the fact that she is employed is rarely central to the conflict. And overall, studies show, being employed doesn’t have negative effects on children; carefully done research consistently makes this clear.”
—Grace Baruch (20th century)
“Feeling that you have to be the perfect parent places a tremendous and completely unnecessary burden on you. If we’ve learned anything from the past half-century’s research on child development, it’s that children are remarkably resilient. You can make lots of mistakes and still wind up with great kids.”
—Lawrence Kutner (20th century)
“It is a good morning exercise for a research scientist to discard a pet hypothesis every day before breakfast. It keeps him young.”
—Konrad Lorenz (1903–1989)