Edmonds' algorithmとは 意味・読み方・使い方

In graph theory, a branch of mathematics, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a maximum or minimum optimum branchings. When nodes are connected by weighted edges that are directed, a minimum spanning tree algorithm cannot be used. Instead an optimum branching algorithm should be applied using the algorithm proposed independently first by Yoeng-jin Chu and Tseng-hong Liu (1965) and then by Edmonds (1967). To find a maximum path length, the largest edge value is found and connected between the two nodes, then the next largest value, and so on. If an edge creates a loop, it is erased. A minimum path length is found by starting from the smallest value.