文献

J-GLOBAL ID：201702264817612224   整理番号：17A1149397

動的計画法に基づく無ラベル根なし木の列挙アルゴリズム

A dynamic programming based algorithm for enumerating unlabeled unrooted trees

著者 (3件)： 増井隆治 (京大) ,  SHURBEVSKI Aleksandar (京大) ,  永持仁 (京大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 117  号： 176(COMP2017 13-19)  ページ： 33-40  発行年： 2017年08月11日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本研究では,動的計画法に基づき,与えられた頂点数nの全ての無ラベル根なし木をΟ(n³)領域で1個当たりΟ(n)時間で生成するアルゴリズムを与える。頂点数nの無ラベル根なし木上の全順序を定め,準備段階で木の個数を計算,記憶することを利用しており,k番目の木の情報からk+1番目の木との差分を同定し,その部分のみ作り変えることで,効率的に列挙を行う。(著者抄録)

シソーラス用語： *動的計画法 ,  *木【グラフ】 ,  *アルゴリズム ,  頂点 ,  グラフ理論 ,  *数え上げ理論 ,  数列 ,  集合 ,  CPU時間 ,  ツリー構造 ,  シーケンシャル処理
準シソーラス用語： グラフアルゴリズム ,  Ο(n)時間 ,  順序木

分類 (2件)： 計算理論  (JB02000A) ,  数理計画法  (KA03030M)

引用文献 (15件)：

• M. AMANI AND A. NOWZARI-DALINI, Generation, ranking and unranking of ordered trees with degree bounds, arXiv preprint arXiv:1603.00977, (2016).
• R. ARINGHIERI, P. HANSEN, AND F. MALUCELLI, Chemical trees enumeration algorithms, 4OR: A Quarterly Journal of Operations Research, 1 (2003), pp. 67-83.
• C. BENECKE, R. GRUND, R. HOHBERGER, A. KERBER, R. LAUE, AND T. WIELAND, Molgen+, a generator of con-nectivity isomers and stereoisomers for molecular structure elucidation, Analytica Chimica Acta, 314 (1995), pp. 141-147.
• L. C. BLUM AND J.-L. REYMOND, 970 million druglike small molecules for virtual screening in the chemical universe database gdb-13, Journal of the American Chemical Soci-ety, 131 (2009), pp.8732-8733.
• H. FUJIWARA, J. WANG, L. ZHAO, H. NAGAMOCHI, AND T. AKUTSU, Enumerating treelike chemical graphs with given path frequency, Journal of Chemical Information and Modeling, 48 (2008), pp.1345-1357.

タイトルに関連する用語 (5件)： 動的計画法 ,  ラベル ,  根 ,  木 ,  アルゴリズム