著者
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).

言及状況

外部データベース (ISBN)

Twitter (1 users, 1 posts, 0 favorites)

収集済み URL リスト