| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-05-17 15:05 動的計画法を用いた有向二値完全系統樹の効率のよい列挙 森戸一貴（西部建設）・○斎藤寿樹・山口一章・増田澄男（神戸大）  COMP2013-12 |
|
| 抄録 | （和） | 本論文では，不完全なデータから有向二値完全系統樹の列挙について扱う．近年，Kiyomi らによって，ZDD と呼ばれる組合せ集合をコンパクトに表現するデータ構造を用いた有向二値完全系統樹の列挙アルゴリズムが提案された．ZDD には豊富な演算体系があり，Kiyomi らのアルゴリズムはこれらの演算を用いて，すべての有向二値完全系統樹を保持するZDD を構築する．一方，Knuth によるZDD を用いたグラフ上のパスを列挙する高速なアルゴリズムがある．この手法は動的計画法に基づいており，目的とするZDD のみをトップダウンに構築する．本研究では，Knuth のアイディアを用いて，動的計画法に基づいた有向二値完全系統樹を列挙する効率のよいアルゴリズムを提案し，提案アルゴリズムの有効性を計算機実験により示す． |
| （英） | 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. |
|
| キーワード | （和） | 有向二値完全系統樹 / 列挙アルゴリズム / 動的計画法 / ZDD / / / / |
| （英） | directed binary perfect phylogeny / enumeration algorithm / dynamic programming / ZDD / / / / | |
| 文献情報 | 信学技報, vol. 113, no. 50, COMP2013-12, pp. 63-70, 2013年5月. | |
| 資料番号 | COMP2013-12 | |
| 発行日 | 2013-05-10 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2013-12 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2013-05-17 - 2013-05-18 |
| 開催地（和） | 小樽商科大学 |
| 開催地（英） | Otaru University of Commerce |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2013-05-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | 動的計画法を用いた有向二値完全系統樹の効率のよい列挙 |
| サブタイトル（和） | |
| タイトル（英） | Efficient Enumeration of Directed Binary Perfect Phylogenies using Dynamic Programming |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 有向二値完全系統樹 / directed binary perfect phylogeny |
| キーワード(2)（和/英） | 列挙アルゴリズム / enumeration algorithm |
| キーワード(3)（和/英） | 動的計画法 / dynamic programming |
| キーワード(4)（和/英） | ZDD / ZDD |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 森戸 一貴 / Kazuki Morito / モリト カズキ |
| 第1著者 所属（和/英） | 西部建設株式会社 (略称： 西部建設) SEIBU CONSTRUCTION (略称： SEIBU CONSTRUCTION) |
| 第2著者 氏名（和/英/ヨミ） | 斎藤 寿樹 / Toshiki Saitoh / サイトウ トシキ |
| 第2著者 所属（和/英） | 神戸大学 (略称： 神戸大) Kobe University (略称： Kobe Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 山口 一章 / Kazuaki Yamaguchi / ヤマグチ カズアキ |
| 第3著者 所属（和/英） | 神戸大学 (略称： 神戸大) Kobe University (略称： Kobe Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 増田 澄男 / Sumio Masuda / マスダ スミオ |
| 第4著者 所属（和/英） | 神戸大学 (略称： 神戸大) Kobe University (略称： Kobe Univ.) |
| 講演者 | 第2著者 |
| 発表日時 | 2013-05-17 15:05:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2013-12 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.50 |
| ページ範囲 | pp.63-70 |
| ページ数 | 8 |
| 発行日 | 2013-05-10 (COMP) |
[研究会発表申込システムのトップページに戻る]