教師資料查詢 | 類別: 期刊論文 | 教師: 林莊傑 CHUANG-CHIEH LIN (瀏覽個人網頁)

標題:New fixed-parameter algorithms for the minimum quartet inconsistency problem
學年
學期
出版(發表)日期2009/01/27
作品名稱New fixed-parameter algorithms for the minimum quartet inconsistency problem
作品名稱(其他語言)
著者Maw-Shang Chang; Chuang-Chieh Lin; Peter Rossmanith
單位
出版者
著錄名稱、卷期、頁數Theory of Computing Systems 47, pp.342–367
摘要Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4k n+n 4). In this paper, first we present an O(3.0446k n+n 4) fixed-parameter algorithm and an O(2.0162k n 3+n 5) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O *((1+ε)k) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant.
關鍵字Evolutionary tree;Quartet topology;Leaf-labeled tree;Minimum quartet inconsistency problem;Fixed-parameter algorithm;Depth-bounded search tree
語言英文(美國)
ISSN1433-0490
期刊性質國內
收錄於SCI;
產學合作
通訊作者Chuang-Chieh Lin
審稿制度
國別美國
公開徵稿
出版型式,電子版,紙本
相關連結
SDGs
  • 優質教育
Google+ 推薦功能,讓全世界都能看到您的推薦!