Edmonds' Algorithm

This past week in CIS 115, we have been talking about algorithms. An algorithm is a procedure that is guaranteed to achieve a goal or produce a correct answer to some sort of problem every time. (The Pattern on the Stone by W. Daniel Hillis p.78)  The first algorithms we discussed in class were sorting algorithms: Bubble, Quick, Merge, and Insertion. Each of these can be easy simulated with a deck of cards and will all result in the same conclusion where the cards are sorted from 2-A (low to high) but are varied in their run times and some work better in different situations. For instance, the average run time for quick sort is n(log(n)) but it has the worst possible outcome of n^2 where n is the number of data present. The worst case possible for insertion and bubble sort is also n^2 while the merge sort worst case scenario is only n(log(n)). Generally speaking, algorithms exist solely to make work easier for people and computers. In fact, one of the books we are reading in class is titled Nine Algorithms That Changed the Future by John MacCormick. This book goes in depth on the following algorithms: Euclid's Algorithm which finds the greatest common denominator, Dijkstra's shortest-path algorithm, the nearest-neighbor algorithm, as well as a few others which have shaped coding, databases, and digital signatures. Some of the more common algorithms have to do with sequencing data, sorting data, calculations, and graphs. One algorithm I am specifically interested in that assists in graphing is called Edmonds' Algorithm. This algorithm was first presented Yoeng-Jin Chu and Tseng-Hong Liu in 1965 and was later presented again by Jack Edmonds in 1967; Edmonds' Algorithm is used to find the maximum and minimum points in branching. (https://en.wikipedia.org/wiki/Edmonds%27_algorithm) The purpose of Edmonds' Algorithm is to take D = (V,E) where D is a directed graph, V is the set of nodes, and E is the set of edges while the root (r) and weight (w) make up E to find the arborescence (A) in the cycles (C) and (u,v) make up the edges. (https://en.wikipedia.org/wiki/Edmonds%27_algorithm) To understand this, people need to first understand what arborescence is. Arborescence is a directed graph (D) with one direct path from u to v. There are three possible outcome for this, one where the edge (u,v) goes towards the cycle (C), one where the edge goes away from the cycle, and lastly one where the edge is unrelated to the cycle. The first one, where the edge goes towards the cycle requires a new edge (E') to be created with the formula w'(e) = w(u,v) - w(pi(v),v). Both others result in a new edge with the formula w'(e) = w(u,v).(https://en.wikipedia.org/wiki/Edmonds%27_algorithm) Once both edges are present, E and E', the algorithm can be used to find the minimum spanning between A' and D' by observing f(D, r, w) and f(D', r, w'). The run time for this algorithm is O(EV) but has been modified a few different times over the years to have some faster and more efficient run times of O(ElogV), O(V^2), and O(E + VlogV). (https://en.wikipedia.org/wiki/Edmonds%27_algorithm) This algorithm, though interesting, is difficult to grasp at this time being that I have no purpose for it nor a way to test it for myself. Even though I have no reason to use this right now, Edmonds' Algorithm is a key component of algorithmic graph theory and has been for roughly 50 years. Without Edmonds' Algorithm, certain graphical data would require more people and time to calculate.