Galactic algorithm: Difference between revisions

Revision as of 02:58, 9 March 2023

Revision as of 03:03, 9 March 2023

Line 42:

=== Minimum Spanning Trees ===

The [[expected linear time MST 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 of the graph.<ref>{{Cite journal |last1=Karger |first1=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 |journal=Journal of the ACM |volume=42 |issue=2 |pages=321–328 |doi=10.1145/201019.201022 |issn=0004-5411|doi-access=free }}</ref> However, the constant factor that is hidden by the [[Big O notation]] is huge enough to make the algorithm impractical. An implementation is publicly available<ref>{{Cite web |last=Thiesen |first=Francisco |title=kargerA C++ implementation for an Expected Linear-kleinTime Minimum Spanning Tree Algorithm(Karger-tarjanKlein-Tarjan + Hagerup Minimum Spanning Tree Verification as a sub-routine) |url=https://github.com/FranciscoThiesen/karger-klein-tarjan |access-date=2022-11-19 |website=[[GitHub]]}}</ref> 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 \cdot 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>

== References ==