View source for Directed (Optimum Branchings), General MST

{{DISPLAYTITLE:Directed (Optimum Branchings), General 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'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.

== Related Problems == 

Subproblem: [[Directed (Optimum Branchings), Super Dense MST]]

Related: [[Undirected, General MST]], [[Undirected, Dense MST]], [[Undirected, Planar MST]], [[Undirected, Integer Weights 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

|-

| [[Chu-Liu-Edmonds Algorithm (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST))|Chu-Liu-Edmonds Algorithm]] || 1965 || $O(EV)$ || $O(E+V)$ || Exact || Deterministic || [https://nvlpubs.nist.gov/nistpubs/jres/71b/jresv71bn4p233_a1b.pdf Time]
|-
| [[Tarjan (directed, general) (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST))|Tarjan (directed, general)]] || 1987 || $O(ElogV)$ || $O(E)$ || Exact || Deterministic || [https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103 Time & Space]
|-
| [[Gabow, Galil, Spencer (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST))|Gabow, Galil, Spencer]] || 1984 || $O(VlogV+Eloglog(logV/log(E/V + {2})$)) || $O(E)$ || Exact || Deterministic || [https://ieeexplore.ieee.org/abstract/document/715935 Time]
|-
| [[Gabow et al, Section 3 (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST))|Gabow et al, Section 3]] || 1986 || $O(E+VlogV)$ || $O(E+V)$ || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF02579168 Time]
|-
|}

== References/Citation == 

https://link.springer.com/article/10.1007/BF02579168