最小共通包含木問題に対する並列近似アルゴリズム

元データ 1994-01-25 社団法人情報処理学会

概要

最小共通包含木(Minimum Common Supertree)問題は与えられたラベル付き完全k分木の集合に対し,その全ての木を部分木として含む辺数最小のk分木を求める問題である.この問題はNP困難な問題であることが示されている.本稿では,この問題に対する多項式時間近似アルゴリズムを与える.さらに,このアルゴリズムによって最適解の1+1/(2k-2)倍以下の大きさの解を求めることができることを示す.また,この近似アルゴリズムを並列化し,並列近似アルゴリズムとしての計算量も評価する.

著者

中野 浩嗣 (株)日立製作所基礎研究所
宮野 悟 九州大学理学部基礎情報学研究施設
山口 敦子 (株)日立製作所基礎研究所
山口 敦子 日立製作所基礎研究所:(現)生物分子工学研究所

関連論文

▼もっと見る