Content deleted Content added
Taking the time to add yet another example of galactic algorithm. I implemented Karger-Klein-Tarjan for my CS undergrad thesis, and even though it is linear in the size of the graph, it has HUGE constants. |
m Adding missing reference link for the Karger-Klein-Tarjan algorithm |
||
Line 42:
=== Minimum Spanning Trees ===
The [[Expected linear time MST algorithm|Karger-Klein-Tarjan]] algorithm is able to discover the [[Minimum spanning tree]] of a graph in <math>O(m + n)</math> where <math>m</math> is the number of edges and <math>n</math> is the number of nodes.<ref>{{Cite journal |last=Karger |first=David R. |last2=Klein |first2=Philip N. |last3=Tarjan |first3=Robert E. |date=1995-03-01 |title=A randomized linear-time algorithm to find minimum spanning trees |url=https://doi.org/10.1145/201019.201022 |journal=Journal of the ACM |volume=42 |issue=2 |pages=321–328 |doi=10.1145/201019.201022 |issn=0004-5411}}</ref> However, the constant factor that is hidden by the [[Big O notation]] is huge enough to make the algorithm impractical. It's implementation is publicly available at [https://github.com/FranciscoThiesen/karger-klein-tarjan here] and given the experimentally estimated implementation constants, it would only be faster than [[Borůvka's algorithm]] for graphs in which <math>m + n > 9 * 10^{151}</math>.<ref>{{Cite web |last=Geiman Thiesen |first=Francisco |title=Expected Linear-Time Minimum Spanning Trees |url=https://franciscothiesen.github.io/Linear-Time-MST/ |access-date=2022-11-13 |website=franciscothiesen.github.io}}</ref>
| |||