Content deleted Content added
LouScheffer (talk | contribs) →Matrix multiplication: Add parenthesis to a parenthetical phrase |
LouScheffer (talk | contribs) →Minimum Spanning Trees: Better math formatting. '*' for multiplication is normal for computer languages, but not usual in mathematics |
||
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 |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. An implementation is publicly available<ref>{{Cite web |last=Thiesen |first=Francisco |title=karger-klein-tarjan |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
== References ==
| |||