著者

El Bekkaye Mermri Katagiri Hideki Sakawa Masatoshi Kato Kosuke

出版者

JAIST Press

巻号頁・発行日

2005-11

---

Let G be a complete undirected graph with n vertices, e edges and m spanning trees. In this paper we give an algorithm for finding explicitly all spanning trees of G. Our technique is based on the representation of spanning trees by Prufer numbers. To represent all Prufer numbers with n - 2 digits we define what we call base-n. The algorithm requires a time of O(nm) and space of O(n). For finding all spanning trees explicitly of undirected graphs, the best known algorithm requires a time of O(e + n + nm) and space of O(e + n).