Jack Edmonds

Jack R. Edmonds ( born April 5, 1934) is a Canadian computer scientist and mathematician who deals with combinatorial optimization.

Edmonds graduated from the George Washington University with a bachelor's degree in 1958 and at the University of Maryland with a Master 's degree in 1959. Afterwards he worked until 1969 in the Department of Operations Research at the National Bureau of Standards under Alan Goldman. From 1969 he was professor at the University of Waterloo. He taught there until his retirement in 1999, except for a period from 1991 to 1993, in which he was involved in a dispute with the University over a purported letter of resignation.

From him and Richard M. Karp comes to the algorithm of Edmonds and Karp. In 1965 he published the first polynomzeitlichen algorithm for the matching problem in graph theory (algorithm of Edmonds ). He is also known for the structure set of Tibor Gallai and Edmonds ( Edmonds - Gallai and decomposition ), the maximum matching describes, for contributions to the theory of matroids and Optimal branches (Optimum Branchings ).

With Ellis L. Johnson, he solved the postman problem (Chinese Postman Problem ) with matching methods. They showed that it is solvable in polynomial time ( in contrast to the seemingly similar, but far more difficult problem of a Salesman ).

In 1985 he was awarded the John von Neumann Theory Prize.