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
