One of his earliest and 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 use of linear programming ideas in combinatorial optimization. It sealed in the importance of there being proofs, or "witnesses", that the answer for an instance is yes and there being proofs, or "witnesses", that the answer for an instance is no. In this blossom algorithm paper, Edmonds also characterizes feasible problems as those solvable in polynomial time; this is one of the origins of the Cobham–Edmonds thesis.