Undirected, Dense MST
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. ).
Parameters
- : number of vertices
- : number of edges
- : maximum edge weight
Filters
Computational Model
Randomization
Approximation
Algorithms Table
Displaying 1 of 1 algorithms
| See more | ||||
|---|---|---|---|---|
| Cheriton-Tarjan (dense) | 1976 | O(E) | O(E) auxiliary |
Reductions Table
Insuffient Data to display table
Other relevant algorithms
Insuffient Data to display table