Edge-disjoint spanning trees and depth-first search

Research output: Contribution to journalArticle

82 Scopus citations

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 depthfirst search and an efficient method for computing disjoint set unions. It requires O (eα(e, n)) time and O(e) space to analyze a graph with n vertices and e edges, where α (e, n) is a very slowly growing function related to a functional inverse of Ackermann's function.

Original languageEnglish (US)
Pages (from-to)171-185
Number of pages15
JournalActa Informatica
Volume6
Issue number2
DOIs
StatePublished - Jun 1 1976
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Edge-disjoint spanning trees and depth-first search'. Together they form a unique fingerprint.

  • Cite this