Reports
Finding All Spanning Trees of Undirected and Directed Graphs ; CU-CS-103-77 Public Deposited
https://scholar.colorado.edu/concern/reports/qj72p7673
- Abstract
- An algorithm for finding all spanning trees (arborescences) of a directed graph is presented. It uses backtracking and a method for detecting bridges based on depth-first search. The time required is 0(V+E+EN) and the space is 0(V+E), where V, E, and N represent the number of vertices, edges, and spanning trees, respectively. If the graph is undirected, the time is actually 0(V+E+VN), which is optimal to within a constant factor. The previously best known algorithm for undirected graphs requires time 0(V+E+EN).
- Creator
- Date Issued
- 1977-01-01
- Academic Affiliation
- Last Modified
- 2019-12-21
- Resource Type
- Rights Statement
- Language
Relationships
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
findingAllSpanningTreesOfUndirectedAndDirectedGraphsCu.pdf | 2019-12-21 | Public | Download |