Edge-Disjoint Spanning Trees, Dominators, and Depth-First Search.
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 OV log VE time and OVE space to analyze a graph with V vertices and E edges. Author
- Theoretical Mathematics