Efficiently Computing Directed Minimum Spanning Trees

Maximilian Böther, Otto Kißig, Christopher Weyand

Computing a directed minimum spanning tree, called arborescence, is a fundamental algorithmic problem, although not as common as its undirected counterpart. In 1967, Edmonds discus…