View source for Undirected, General MST

{{DISPLAYTITLE:Undirected, General MST (Minimum Spanning Tree (MST))}}
== Description == 

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, there are no restrictions on edge weights or graph density.

== Related Problems == 

Subproblem: [[Undirected, Dense MST]], [[ Undirected, Planar MST]], [[ Undirected, Integer Weights MST]]

Related: [[Undirected, Planar MST]], [[Undirected, Integer Weights MST]], [[Directed (Optimum Branchings), General MST]], [[Directed (Optimum Branchings), Super Dense MST]]

== Parameters == 

V: number of vertices

E: number of edges

U: maximum edge weight

== Table of Algorithms == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Kruskal’s algorithm with demand-sorting (Undirected, General MST Minimum Spanning Tree (MST))|Kruskal’s algorithm with demand-sorting]] || 1991 || $O(Elog(V)$) || $O(E)$ auxiliary || Exact || Deterministic || [https://link-springer-com.ezproxy.canberra.edu.au/chapter/10.1007/BFb0028279 Time]
|-
| [[Quick Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Quick Kruskal algorithm]] || 2006 || $O(Elog(V)$) || $O(E)$ auxiliary || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/citation.cfm?id=2791187 Time]
|-
| [[Karger; Klein & Tarjan (Undirected, General MST Minimum Spanning Tree (MST))|Karger; Klein & Tarjan]] || 1995 || $O(min(V^{2}, ElogV)$) || $O(E)$ auxiliary || Exact || Randomized || [http://cs.brown.edu/research/pubs/pdfs/1995/Karger-1995-RLT.pdf Time]
|-
| [[Borůvka's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Borůvka's algorithm]] || 1926 || $O(ElogV)$ || $O(V)$ auxiliary || Exact || Deterministic ||  
|-
| [[Prim's algorithm + adjacency matrix searching (Undirected, General MST Minimum Spanning Tree (MST))|Prim's algorithm + adjacency matrix searching]] || 1957 || $O(V^{2})$ || $O(V)$ auxiliary || Exact || Deterministic || [https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/document/6773228 Time]
|-
| [[Prim's algorithm + Fibonacci heaps; Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST))|Prim's algorithm + Fibonacci heaps; Fredman & Tarjan]] || 1987 || $O(E + VlogV)$ || $O(V)$ auxiliary? || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/citation.cfm?id=28874 Time]
|-
| [[Kruskal's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Kruskal's algorithm]] || 1956 || $O(ElogE)$ || $O(E)$ auxiliary || Exact || Deterministic || [https://www-jstor-org.ezproxy.canberra.edu.au/stable/2033241 Time]
|-
| [[Yao's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Yao's algorithm]] || 1975 || $O(EloglogV)$ || $O(E)$ auxiliary? || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0020019075900563 Time]
|-
| [[Cheriton-Tarjan Algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Cheriton-Tarjan Algorithm]] || 1976 || $O(EloglogV)$ || $O(E)$ auxiliary? || Exact || Deterministic || [https://epubs-siam-org.ezproxy.canberra.edu.au/doi/abs/10.1137/0205051 Time]
|-
| [[Filter Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Filter Kruskal algorithm]] || 2009 || $O(Elog(V))$ || $O(E)$ auxiliary? || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/citation.cfm?id=2791225 Time]
|-
| [[Chazelle's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Chazelle's algorithm]] || 2000 || $O(E*\alpha(E, V))$ || $O(E)$ auxiliary?? || Exact || Deterministic || [https://www.cs.princeton.edu/~chazelle/pubs/mst.pdf Time]
|-
| [[Thorup (reverse-delete) (Undirected, General MST Minimum Spanning Tree (MST))|Thorup (reverse-delete)]] || 2000 || $O(E LogV (loglogV)^{3})$ || $O(E)$ auxiliary? || Exact || Deterministic || [https://www.cs.princeton.edu/courses/archive/spr10/cos423/handouts/NearOpt.pdf Time]
|-
| [[Bader & Cong Parallel Implementation  (Undirected, General MST Minimum Spanning Tree (MST))|Bader & Cong Parallel Implementation ]] || 2006 || $O(E log(V)$/p) || $O(V)$ total || Exact || Parallel || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/S0743731506001262 Time]
|-
| [[Prim's algorithm + binary heap (Undirected, General MST Minimum Spanning Tree (MST))|Prim's algorithm + binary heap]] || - || $O(ElogV)$ || $O(V)$ auxiliary? || Exact || Deterministic ||  
|-
| [[Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST))|Fredman & Tarjan]] || 1987 || $O(E*beta(E, V)$) where beta(m, n) = min(i such that log^(i)(n)≤m/n); this is also $O(E (log-star)$V) || $O(E)$ auxiliary? || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/citation.cfm?id=28874 Time]
|-
| [[Gabow et al, Section 2 (Undirected, General MST Minimum Spanning Tree (MST))|Gabow et al, Section 2]] || 1986 || $O(E*log(beta(E, V)$)) || $O(E)$ auxiliary? || Exact || Deterministic || [https://link-springer-com.ezproxy.canberra.edu.au/article/10.1007/BF02579168 Time]
|-
| [[Pettie, Ramachandran (Undirected, General MST Minimum Spanning Tree (MST))|Pettie, Ramachandran]] || 2002 || unknown but optimal || $O(E)$ auxiliary? || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/505241.505243 Time]
|-
|}

== Time Complexity Graph == 

[[File:Minimum Spanning Tree (MST) - Undirected, General MST - Time.png|1000px]]

== Space Complexity Graph == 

[[File:Minimum Spanning Tree (MST) - Undirected, General MST - Space.png|1000px]]

== Pareto Frontier Improvements Graph == 

[[File:Minimum Spanning Tree (MST) - Undirected, General MST - Pareto Frontier.png|1000px]]

== References/Citation == 

https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/505241.505243 

https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/505241.505243