EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH

スポンサーリンク

概要

• 論文の詳細を見る

• Let G be an undirected graph with V vertices and E edges. We consider the problem of enumerating all spanning trees of G. In order to explicitly output all spanning trees, the output size is of Θ(NV), where N is the number of spanning trees. This, however, can be compressed into Θ(N) size. In this paper, we propose a new algorithm for enumerating all spanning trees of G in such compact form. The time and space complexities of our algorithm are O(N + V + E) and O(VE), respectively. The algorithm is optimal in the sense of time complexity.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Tamura Akihisa

  Department Of Mathematics Keio University

• Tamura Akihisa

  Department Of Computer Science And Information Mathematics The University Of Electro-communications

• Shioura Akiyoshi

  Tokyo Institute of Technology

• Shioura A

  Tohoku Univ. Sendai‐shi Jpn

関連論文

• A Semidefinite Programming Relaxation for the Generalized Stable Set Problem(Discrete Mathematics and Its Applications)
• THE GENERALIZED STABLE SET PROBLEM FOR PERFECT BIDIRECTED GRAPHS
• EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
• Efficiently scanning all spanning trees of an undirected graph.
• Matching with partially ordered contracts

スポンサーリンク