Paths, Trees, and Flowers

Edmonds. (1965). Paths, Trees, and Flowers.

Type

Journal article

Intellectual base

Primary research

Year

1965

DOI

10.4153/cjm-1965-045-4

Link

https://doi.org/10.4153/cjm-1965-045-4

Cited by

1 citation across 1 artifact.

Domain-specific

• Matching
  • Edmonds's blossom algorithm (1965) finds maximum matchings in general graphs in polynomial time — \(O(|V|^4)\) in Edmonds's own analysis, sharpened to \(O(|V|^3)\) by Gabow (1976) — a foundational result in combinatorial optimization partly because the algorithm introduced the technique of shrinking odd cycles (blossoms) to handle the non-bipartite case

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:31a41e810e72 · see in the full table