An algorithm for enumerating all spanning trees of a directed graph

An algorithm for enumerating all spanning trees of a directed graph

0.00 Avg rating0 Votes
Article ID: iaor2002361
Country: United States
Volume: 27
Issue: 2
Start Page Number: 120
End Page Number: 130
Publication Date: Jun 2000
Journal: Algorithmica
Authors: ,
Keywords: minimum spanning trees
Abstract:

We present an O(NV + V³) time algorithm for enumerating all spanning trees of a directed graph. This improves the previous best known bound of O(NE + V + E) when V²=o(N), which will be true for most graphs. Here, N refers to the number of spanning trees of a graph having V vertices and E edges. The algorithm is based on the technique of obtaining one spanning tree from another by a series of edge swaps. This result complements the result in the companion paper which enumerates all spanning trees in an undirected graph in O(N + V + E) time.

Reviews

Required fields are marked *. Your email address will not be published.