不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
スポンサーリンク
概要
- 論文の詳細を見る
不完全なデータが与えられたときに,形質に基づいて系統樹を復元する問題を研究する.より正確には,形質が二値であり,有向完全系統樹の仮定が成り立つ場合に,ある種に対してある形質の状態がデータとして失われている状況を考える.本研究の目的は失われたデータを補完したときに得られる完全系統樹をすべて列挙するための効率的アルゴリズムを設計することである.単純な分枝限定アルゴリズム(B&B)は理論的に良い計算量を持つが,ゼロサプレス型二分決定グラフ(ZDD)に基づく別の方法を提案する.ランダム生成されたデータに対する実験では,ZDDに基づく手法がB&Bよりも優れた結果を示した.また,与えられた不完全データと矛盾しない完全系統樹の数を計算する問題が#P完全であることを示し,すなわち,効率的標本抽出が難しいことの傍証を与える.
- 一般社団法人電子情報通信学会の論文
- 2012-06-14
著者
-
岡本 吉央
東京工業大学情報理工学研究科
-
斎藤 寿樹
北陸先端科学技術大学院大学情報科学研究科
-
岡本 吉央
東京工業大学
-
岡本 吉央
豊橋技術科学大学情報工学系
-
岡本 吉央
東大総合文化
-
岡本 吉央
ETH Zurich
-
岡本 吉央
東京大学大学院総合文化研究科
-
清見 礼
北陸先端科学技術大学院大学
-
岡本 吉央
北陸先端科学技術大学院大学大学院教育イニシアティブセンター
-
岡本 吉央
電気通信大学大学院情報理工学研究科情報・通信工学専攻
-
斎藤 寿樹
神戸大学大学院工学研究科電気電子工学専攻
-
岡本 吉央
北陸先端科学技術大学院大学 大学院教育イニシアティブセンター
-
岡本 吉央
電気通信大学
-
斎藤 寿樹
神戸大学大学院工学研究科
-
清見 礼
横浜市立大学国際総合科学部
-
斎藤 寿樹
神戸大学大学院
-
清見 礼
横浜市立大学 国際総合科学部
関連論文
- 絵画的迷路作成アルゴリズムの改善 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 嘘を含む比較による最小値最大値発見アルゴリズム (アルゴリズムと計算機科学の数理的基盤とその応用)
- 区間二部グラフの効率の良い認識に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- Bipartite Permutation Graphのランダム生成と列挙
- 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
- フォン・ノイマン (特集 現代数学に影響を与えた数学者)
- エレガントな解答をもとむ 解答--出題 2009年10月号
- 1-D-5 最小費用全域木ゲームにおけるシャープレイ値計算の困難性(離散アルゴリズム(2))
- Complexity of pleat folding (理論計算機科学の深化と応用--RIMS研究集会報告集)
- Reconstruction of Connected Interval Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- じゃばら折りの複雑さに関する研究
- 区間表現からMPQ-treeを効率よく構成するアルゴリズム
- 区間表現からMPQ-tree を効率よく構成するアルゴリズム(計算機科学の理論とその応用)
- 絵画的迷路の作り方 (理論計算機科学の深化と応用)
- コーダルグラフの独立点集合の数えあげ問題
- コーダルグラフサンドイッチ問題とその応用
- スーパーコンピューティング・コンテスト2010
- 第18回RAMPシンポジウムルポ(情報の窓)
- ネヴァンリンナ賞業績紹介 スピールマン (特集 国際数学者会議2010)
- 終わりなき旅 (特集 数学者の見た夢)
- グラフクラスと部分グラフ同型性
- 重み付きグラフにおける石移動ゲームについて
- 支配集合数え上げ問題とグラフクラス
- 最小費用全域木ゲーム(OR事典Wiki)
- 完全グラフ上の最大辺素パス問題に対する貪欲近似アルゴリズム (最適化の数理とアルゴリズム)
- 凸幾何に対する貪欲算法 (最適化の数理科学)
- 嘘を含む比較による最小値最大値発見アルゴリズム
- パス上のボロノイゲーム
- 第4回 離散最適化と協力ゲーム(2)(離散最適化とその応用)
- 電力取り引きにおける約定量決定問題の高速解法
- 電力取り引きにおける約定量決定問題の高速解法(組合せ最適化(5))
- 双二次最終多項式による有向マトロイドの実現不可能性判定
- Non-LP orientations, non-line shellings, and non-representable oriented matroids
- 「Cellチャレンジ2009」実施報告
- Nearest Larger Neighbors問題に対する効率の良いアルゴリズム (理論計算機科学の深化と応用)
- 適応的計算幾何 (計算幾何学と離散数学)
- 「Cell チャレンジ2009」実施報告
- 第56回シンポジウムルポ(情報の窓)
- 2B07 カリキュラムの学際性を計量する : カリキュラムの数量的分析の試み
- アンチマトロイドのサーキットとDilworthの分解定理 (情報学シンポジウム特集号)
- 固定パラメータ容易性(新・ORの図解,学会創立50周年記念号)
- グラフクラスにおける森の数え上げに対する高速指数時間アルゴリズム(セッション3)
- 離散最適化に対する高速な厳密アルゴリズム(OR研究の最前線)
- Submodularity of some classes of the combinatorial optimization games
- 組合せ最適化理論の三次元描像 (第21回 回路とシステム軽井沢ワークショップ論文集) -- (新世代の計算限界)
- 凸幾何上の協力ゲームにおけるコアの安定性(ゲーム)
- 二分タングルグラムの描き方 (列挙問題に対する計算の高速化と可視化)
- コンピュータサイエンス教科書シリーズ19数理計画法, 加藤直樹(著), コロナ社(2008-01), A5判, 定価(本体2,800円+税)
- コーダルサンドイッチの列挙, ランダム生成, 数え上げについて (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 反転数を考慮したクイックソートの計算量解析
- 2-F-5 多目的最適化への列挙アルゴリズム理論からのアプローチ(数理計画(1))
- ZDD によるパスの列挙 (計算機科学とアルゴリズムの数理的基礎とその応用)
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- 間違えても大丈夫な凸包構成アルゴリズム
- 等間隔の折り目を持つ紙の折り畳みの計算量について
- 複数の単位円による点集合の排他的被覆
- ZDDを用いたパスの列挙とその性能評価
- 定数ラウンドで復元可能な合理的秘密分散
- DS-1-16 弦グラフおよびその部分クラスの列挙(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- コーダルグラフのサンドイッチ列挙
- 1-B-14 線形計画問題を誤差無く解くソルバ(数理計画(1))
- 高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- レベル付き木の描画における頂点角解像度と交差角解像度
- Rational Secret Sharing for Non-Simultaneous Channels (情報理論)
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- 5.ZDDを用いた新たな列挙手法(広がる列挙の技術-列挙による問題解決アプローチ-)
- 1.列挙の基本と基礎的なアルゴリズム(広がる列挙の技術-列挙による問題解決アプローチ-)
- DK-2-2 フロンティア法の種々のリンクパズル問題への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-2 フロンティア法の種々のリンクパズル問題への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- 非協力ゲーム(基礎編)
- 『計算機科学者のためのゲーム理論入門』シリーズについて
- 施設配置ゲームにおける仁・シャープレイ値の計算について (Theoretical Foundations of Computing)
- 大学院における研究室教育の構造化へ向けて (II. 活動報告 . (2) 質保証枠組みの方策)
- 非協力ゲーム(発展編)
- JAIST創立20周年記念シンポジウム報告 (III. センター関連イベント報告 . (1) JAIST創立20周年記念シンポジウム)
- 4つの教育ポリシー&ガイドラインを基盤としたJAISTにおける国際的質保証に向けた提案 (II. 活動報告 . (2) 質保証枠組みの方策)
- メカニズムデザイン(基礎編)
- ZDDを用いた新たな列挙手法
- 費用2種類の施設配置ゲームの仁とシャープレイ値の計算について
- 非同時通信路における合理的秘密分散(情報セキュリティ)
- 動的計画法を用いた有向二値完全系統樹の効率のよい列挙
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- グラフを通したパズル・ゲームの一般化(娯楽のOR)
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- 施設配置ゲームにおける仁・ジャープレイ値の計算について
- エレガントな解答をもとむ 解答 : 出題 2013年2月号
- 近似のアルゴリズムと数理計画法 : 最近の進展 (特集 P≠NP予想最前線)
- Computational complexity and an integer programming model of Shakashaka (コンピュテーション)
- 動的計画法を用いた上界計算法による最大重みクリーク抽出アルゴリスムの提案(一般)
- 動的計画法を用いた有向二値完全系統樹の効率のよい列挙(一般)
- 階層グラフの直交描画アルゴリズム
- ペンシルパズル「シャカシャカ」の計算複雑さと整数計画モデル
- 『計算機科学者のためのゲーム理論入門』シリーズ第4回 : メカニズムデザイン(応用編)
- 境界上の重みの釣合せ (計算理論とアルゴリズムの新潮流)
- On the t-pebbling number of weighted graphs (アルゴリズム(AL) Vol.2010-AL-130)
- 協力ゲーム
- 非同時通信路における合理的秘密分散
- 階層グラフの直交描画アルゴリズム(グラフとネットワーク)