Accession Number:
ADA000083
Title:
Edge-Disjoint Spanning Trees, Dominators, and Depth-First Search.
Descriptive Note:
Technical rept.,
Corporate Author:
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Personal Author(s):
Report Date:
1974-09-01
Pagination or Media Count:
42.0
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 OV log VE time and OVE space to analyze a graph with V vertices and E edges. Author
Descriptors:
Subject Categories:
- Theoretical Mathematics