Undirected, Planar 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 planar.
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 (planar) | 1976 | O(V) | O(V) auxiliary |
Reductions Table
Insuffient Data to display table
Other relevant algorithms
Insuffient Data to display table