Edmonds' algorithm
Algorithm for the directed version of the minimum spanning tree problem / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Edmonds' algorithm?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
This article is about the optimum branching algorithm. For the maximum matching algorithm, see Blossom algorithm.
In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching). It is the directed analog of the minimum spanning tree problem. The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967).