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:
“Men talk, but rarely about anything personal. Recent research on friendship ... has shown that male relationships are based on shared activities: men tend to do things together rather than simply be together.... Female friendships, particularly close friendships, are usually based on self-disclosure, or on talking about intimate aspects of their lives.”
—Bettina Arndt (20th century)
“The research on gender and morality shows that women and men looked at the world through very different moral frameworks. Men tend to think in terms of “justice” or absolute “right and wrong,” while women define morality through the filter of how relationships will be affected. Given these basic differences, why would men and women suddenly agree about disciplining children?”
—Ron Taffel (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)