WEKO3
アイテム
動的計画法を用いた有向二値完全系統樹の効率のよい列挙
https://ipsj.ixsq.nii.ac.jp/records/91773
https://ipsj.ixsq.nii.ac.jp/records/91773718fa4a7-7e23-4ce8-8350-17c01782ae89
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL13144010.pdf (592.3 kB)
2100年1月1日からダウンロード可能です。
|
Copyright (c) 2013 by the Institute of Electronics, Information and Communication Engineers
This SIG report is only available to those in membership of the SIG. |
|
| AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-05-10 | |||||||
| タイトル | ||||||||
| タイトル | 動的計画法を用いた有向二値完全系統樹の効率のよい列挙 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Efficient Enumeration of Directed Binary Perfect Phylogenies using Dynamic Programming | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 西部建設株式会社 | ||||||||
| 著者所属 | ||||||||
| 神戸大学大学院工学研究科 | ||||||||
| 著者所属 | ||||||||
| 神戸大学大学院工学研究科 | ||||||||
| 著者所属 | ||||||||
| 神戸大学大学院工学研究科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| SEIBU CONSTRUCTION CO.,LTD. | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kobe University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kobe University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kobe University | ||||||||
| 著者名 |
森戸, 一貴
× 森戸, 一貴
|
|||||||
| 著者名(英) |
Kazuki, Morito
× Kazuki, Morito
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本論文では，不完全なデータから有向二値完全系統樹の列挙について扱う．近年，Kiyomiらによって，ZDDと呼ばれる組合せ集合をコンパクトに表現するデータ構造を用いた有向二値完全系統樹の列挙アルゴリズムが提案された．ZDDには豊富な演算体系があり，Kiyomiらのアルゴリズムはこれらの演算を用いて，すべての有向二値完全系統樹を保持するZDDを構築する．一方，KnuthによるZDDを用いたグラフ上のパスを列挙する高速なアルゴリズムがある．この手法は動的計画法に基づいており，目的とするZDDのみをトップダウンに構築する．本研究では，Knuthのアイディアを用いて，動的計画法に基づいた有向二値完全系統樹を列挙する効率のよいアルゴリズムを提案し，提案アルゴリズムの有効性を計算機実験により示す． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We consider an enumeration of directed binary perfect phylogenies from incomplete data. Recently, Kiyomi et al. proposed an enumeration algorithm for directed binary perfect phylogenies using ZDDs. A ZDD is a compact data structure for a family of sets provided with a rich family of set operations. Kiyomi’s algorithm constructs a ZDD which represents all directed binary perfect phylogenies using these operations. On the other hand, Knuth proposed an algorithm for enumerating paths in a graph by using a ZDD. This method is based on a dynamic programming, and construct the objective ZDD, directly. In this paper, we propose an efficient algorithm for enumerating directed binary perfect phylogenies using the dynamic programming. We show an effectivity of our algorithm by computational experiment. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2013-AL-144, 号 10, p. 1-8, 発行日 2013-05-10 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
