講演抄録/キーワード |
講演名 |
2017-08-18 14:50
動的計画法に基づく無ラベル根なし木の列挙アルゴリズム ○増井隆治・シュルベフスキ アレクサンダル・永持 仁(京大) COMP2017-17 |
抄録 |
(和) |
本研究では, 動的計画法に基づき, 与えられた頂点数$n$の全ての無ラベル根なし木を$mathcal{O}(n^3)$領域で1個当たり$mathcal{O}(n)$時間で生成するアルゴリズムを与える. 頂点数$n$の無ラベル根なし木上の全順序を定め, 準備段階で木の個数を計算, 記憶することを利用しており, $k$番目の木の情報から$k+1$番目の木との差分を同定し, その部分のみ作り変えることで, 効率的に列挙を行う. |
(英) |
We propose a dynamic programming based algorithm for the enumeration of unlabeled and unrooted trees on $n$ vertices. The algorithm generates all such trees without duplication in $O(n)$ time delay per output and $O(n^3)$ space in total. We pre-compute the number of unique trees and define a total order among them. The algorithm generates trees in this order, and achieves high computational efficiency by only updating the different part between two consecutive trees. |
キーワード |
(和) |
グラフ / アルゴリズム / 列挙 / 木 / 動的計画法 / / / |
(英) |
Graph / Algorithm / Enumeration / Tree / Dynamic Programming / / / |
文献情報 |
信学技報, vol. 117, no. 176, COMP2017-17, pp. 33-40, 2017年8月. |
資料番号 |
COMP2017-17 |
発行日 |
2017-08-11 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2017-17 |