Edge-Disjoint Spanning Trees, Dominators, and Depth-First Search.
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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1974
- Accession Number
- ADA000083
Entities
People
- Robert Tarjan
Organizations
- Stanford University