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

Name	Year	Time	Space	Approximation Factor	Model	Reference
Kruskal’s algorithm with demand-sorting	1991	$O(Elog(V)$)	$O(E)$ auxiliary	Exact	Deterministic	Time
Quick Kruskal algorithm	2006	$O(Elog(V)$)	$O(E)$ auxiliary	Exact	Deterministic	Time
Karger; Klein & Tarjan	1995	$O(min(V^{2}, ElogV)$)	$O(E)$ auxiliary	Exact	Randomized	Time
Borůvka's algorithm	1926	$O(ElogV)$	$O(V)$ auxiliary	Exact	Deterministic
Prim's algorithm + adjacency matrix searching	1957	$O(V^{2})$	$O(V)$ auxiliary	Exact	Deterministic	Time
Prim's algorithm + Fibonacci heaps; Fredman & Tarjan	1987	$O(E + VlogV)$	$O(V)$ auxiliary?	Exact	Deterministic	Time
Kruskal's algorithm	1956	$O(ElogE)$	$O(E)$ auxiliary	Exact	Deterministic	Time
Yao's algorithm	1975	$O(EloglogV)$	$O(E)$ auxiliary?	Exact	Deterministic	Time
Cheriton-Tarjan Algorithm	1976	$O(EloglogV)$	$O(E)$ auxiliary?	Exact	Deterministic	Time
Filter Kruskal algorithm	2009	$O(Elog(V))$	$O(E)$ auxiliary?	Exact	Deterministic	Time
Chazelle's algorithm	2000	$O(E*\alpha(E, V))$	$O(E)$ auxiliary??	Exact	Deterministic	Time
Thorup (reverse-delete)	2000	$O(E LogV (loglogV)^{3})$	$O(E)$ auxiliary?	Exact	Deterministic	Time
Bader & Cong Parallel Implementation	2006	$O(E log(V)$/p)	$O(V)$ total	Exact	Parallel	Time
Prim's algorithm + binary heap	-	$O(ElogV)$	$O(V)$ auxiliary?	Exact	Deterministic
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	Time
Gabow et al, Section 2	1986	$O(E*log(beta(E, V)$))	$O(E)$ auxiliary?	Exact	Deterministic	Time
Pettie, Ramachandran	2002	unknown but optimal	$O(E)$ auxiliary?	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff

References/Citation

https://dl.acm.org/doi/10.1145/505241.505243

https://dl.acm.org/doi/10.1145/505241.505243