Directed (Optimum Branchings), General 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're given a directed graph with a root, and we wish to find a spanning arborescence of minimum weight that is rooted at the root.
Parameters
- : number of vertices
- : number of edges
- : maximum edge weight
Filters
Computational Model
Randomization
Approximation
Algorithms Table
Displaying 4 of 4 algorithms
| See more | ||||
|---|---|---|---|---|
| Tarjan (directed, general) | 1987 | O(ElogV) | O(E) | |
| Gabow et al, Section 3 | 1986 | O(E+VlogV) | O(E+V) | |
| Gabow, Galil, Spencer | 1984 | O(VlogV+Eloglog(logV/log(E/V + 2))) | O(E) | |
| Chu-Liu-Edmonds Algorithm | 1965 | O(EV) | O(E+V) |
Reductions Table
Insuffient Data to display table
Other relevant algorithms
Insuffient Data to display table