Report Number: CS-TR-74-455
Institution: Stanford University, Department of Computer Science
Title: Edge-disjoint spanning trees, dominators, and depth-first search.
Author: Tarjan, Robert Endre
Date: September 1974
Abstract: 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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/74/455/CS-TR-74-455.pdf