Edge-disjoint spanning trees, dominators, and depth-first search.
Robert Endre Tarjan · 1974
This paper presents an algorithm for finding two edge-disjoint spanning trees rooted at a fixed vertex of a directed graph. The algorithm uses depth-first search, an efficient method for computing disjoint set unions, and an efficient method for computing dominators. It requires O(V log V + E) time and O(V + E) space to analyze a graph with V vertices and E edges.