Edmonds' algorithm, also called the Chu-Liu/Edmonds algorithm, finds a spanning arborescence of minimum weight in a directed graph, the directed counterpart of the minimum spanning tree problem. It was proposed independently by Yoeng-Jin Chu and Tseng-Hong Liu in 1965 and by Jack Edmonds in 1967.
Facts
Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Connections
Credited To
Source Edmonds' Algorithm (Wikipedia)
In Field
Source Edmonds' Algorithm (Wikipedia)
Invented By
Source Edmonds' Algorithm (Wikipedia)
Uses Design Technique
Source Edmonds' Algorithm (Wikipedia)
Sources
1. Edmonds' Algorithm (Wikipedia)
Wikipedia infobox: time complexity polynomial
polynomial
Credited To: Jack Edmonds, Lead section
and then by Jack Edmonds (1967)
Invented By: Jack Edmonds, Lead section
and then by Jack Edmonds (1967)
In Group: Minimum Spanning Tree Algorithms, Lead
is an algorithm for finding a spanning arborescence of minimum weight
Uses Design Technique: Recursion, Article body
The algorithm has a recursive description.
In Field: Algorithms and Complexity Theory, Lead sentence
Edmonds' algorithm or Chu-Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching).
View the SourceWikidata: Edmonds' Algorithm
Wikidata Q1752324, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.