1978/08/01 by Harold N. Gabow, Eugene W. Myers · 4 citations
Computer Science · Mathematics · #Data Management and Algorithms #Data Visualization and Analytics #Advanced Database Systems and Queries #Combinatorics #Spanning tree #Undirected graph #Mathematics #Backtracking #Connected dominating set #Directed graph #Graph #Discrete mathematics #Algorithm
paper · doi:10.1137/0207024
openalex publication_date 1978/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/10
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 O(V + E + EN) and the space is O(V + E), where V, E, and N represent the number of vertices, edges, and spanning trees, respectively. If the graph is undirected, the time decreases to O(V + E + VN), which is optimal to within a constant factor. The previously best-known algorithm for undirected graphs requires time O(V + E + EN).