View source for Undirected, Dense MST

{{DISPLAYTITLE: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 == 

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

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

|-

| [[Cheriton-Tarjan (dense) (Undirected, Dense MST Minimum Spanning Tree (MST))|Cheriton-Tarjan (dense)]] || 1976 || $O(E)$ || $O(E)$ auxiliary? || Exact || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/0205051 Time]
|-
|}

== References/Citation == 

https://epubs.siam.org/doi/abs/10.1137/0205051