In Asano, T., Igarashi, Y., Nagamochi, H., Miyano, S., & Suri, S., editors, ISAAC 1996: the 7th International Symposium on Algorithms and Computation, volume 1178, of Lecture Notes in Computer Science, pages 166--173, Osaka, Japan, December, 1996. Springer Berlin Heidelberg.
A directed spanning tree in a directed graph G=(V, A) is a spanning tree such that no two arcs share their tails. In this paper, we propose an algorithm for listing all directed spanning trees of G. Its time and space complexities are O(¦A¦+ND(¦V¦, ¦A¦)) and O(¦A¦+DS(¦V¦, ¦A¦)), where D(¦V¦, ¦A¦) and DS(¦V¦, ¦A¦) are the time and space complexities of the data structure for updating the minimum spanning tree in an undirected graph with ¦V¦ vertices and ¦A¦ edges. Here N denotes the number of directed spanning trees in G.
@inproceedings{ Uno1996,
abstract = {A directed spanning tree in a directed graph G=(V, A) is a spanning tree such that no two arcs share their tails. In this paper, we propose an algorithm for listing all directed spanning trees of G. Its time and space complexities are O(¦A¦+ND(¦V¦, ¦A¦)) and O(¦A¦+DS(¦V¦, ¦A¦)), where D(¦V¦, ¦A¦) and DS(¦V¦, ¦A¦) are the time and space complexities of the data structure for updating the minimum spanning tree in an undirected graph with ¦V¦ vertices and ¦A¦ edges. Here N denotes the number of directed spanning trees in G.},
author = {Uno, Takeaki},
booktitle = {ISAAC 1996: the 7th International Symposium on Algorithms and Computation},
doi = {10.1007/BFb0009492},
editor = {Asano, Tetsuo and Igarashi, Yoshihide and Nagamochi, Hiroshi and Miyano, Satoru and Suri, Subhash},
file = {:Users/KunihiroWASA/Dropbox/paper/1996/Uno, An algorithm for enumerating all directed spanning trees in a directed graph, 1996.pdf:pdf},
keywords = {directed spanning tree,enumerating algorithm,listing},
month = {December},
pages = {166--173},
publisher = {Springer Berlin Heidelberg},
series = {Lecture Notes in Computer Science},
title = {{An algorithm for enumerating all directed spanning trees in a directed graph}},
}