Undirected, Dense 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, we assume that the graph is dense (i.e. $E = \Omega(V)$).

Related Problems

Generalizations: Undirected, General 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
Cheriton-Tarjan (dense)	1976	$O(E)$	$O(E)$ auxiliary?	Exact	Deterministic	Time

References/Citation

https://epubs-siam-org.ezproxy.canberra.edu.au/doi/abs/10.1137/0205051