An algorithm for enumerating all spanning trees of a directed graph

Kapoor, S. ; H, Ramesh (2000) An algorithm for enumerating all spanning trees of a directed graph Algorithmica, 27 (2). pp. 120-130. ISSN 0178-4617

Full text not available from this repository.

Official URL: http://link.springer.com/article/10.1007/s00453001...

Related URL: http://dx.doi.org/10.1007/s004530010008

Abstract

We present an O (NV + V3) time algorithm for enumerating all spanning trees of a directed graph. This improves the previous best known bound of O (NE + V+E) [1] when V2 = 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 [3] which enumerates all spanning trees in an undirected graph in O (N+V+E) time.

Item Type:Article
Source:Copyright of this article belongs to Springer Verlag.
Keywords:Spanning Tree; Directed Graph; Enumeration
ID Code:102236
Deposited On:09 Mar 2018 11:20
Last Modified:09 Mar 2018 11:20

Repository Staff Only: item control page