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 language | English (US) |
|---|---|
| Pages (from-to) | 171-185 |
| Number of pages | 15 |
| Journal | Acta Informatica |
| Volume | 6 |
| Issue number | 2 |
| DOIs | |
| State | Published - Jun 1976 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Information Systems
- Computer Networks and Communications