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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE