最小共通包含木問題に対する並列近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
最小共通包含木(Minimum Common Supertree)問題は与えられたラベル付き完全k分木の集合に対し,その全ての木を部分木として含む辺数最小のk分木を求める問題である.この問題はNP困難な問題であることが示されている.本稿では,この問題に対する多項式時間近似アルゴリズムを与える.さらに,このアルゴリズムによって最適解の1+1/(2k-2)倍以下の大きさの解を求めることができることを示す.また,この近似アルゴリズムを並列化し,並列近似アルゴリズムとしての計算量も評価する.
- 社団法人情報処理学会の論文
- 1994-01-25
著者
関連論文
- 正員の例からの最良コンセンサスモチーフの抽出
- アミノ酸配列データからの機械発見システムBONSAI Garden
- 歩行からの次数限定木推論問題
- 最小共通包含木問題に対する並列近似アルゴリズム
- 推論の並列化(計算量理論とその周辺)
- 辞書式順序で最初の極大部分グラフを計算する問題のP完全性とNCアルゴリズム(計算アルゴリズムと計算量の基礎理論)
- 並列知識獲得システムBONSAI Garden
- 形式グラフ体系上の反駁木問題の並列化とグラフ同型問題(計算機構とアルゴリズム)
- 2部グラフ描画問題に対する近似アルゴリズム
- 2部グラフ描画に対する近似アルゴリズム
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- 再構成メッシュ上の最適な初期化アルゴリズム
- Recovery of Incomplete Tables under Data Dependencies (形式言語理論とオ-トマトン理論)
- 並列アルゴリズムの理論
- 並列アルゴリズムの複雑さ
- 並列化とその限界 : 理論的側面から
- 分岐数限定超グラフに対する極大独立集合を求めるNCアルゴリズム
- ゲノム情報における機械学習の計算量 : 理論と実際 (「人工知能技術における計算量」)
- 学習アルゴリズムによるアミノ酸のインデックス化とタンパク質データからの知識獲得実験
- 機械学習理論を適用したアミノ酸配列からの知識獲得
- PAC 学習 : 確率的で近似的に正しい学習 (計算的学習理論とその応用)