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

標題:New fixed-parameter algorithms for the minimum quartet inconsistency problem
學年96
學期2
發表日期2008/05/14
作品名稱New fixed-parameter algorithms for the minimum quartet inconsistency problem
作品名稱(其他語言)
著者Maw-Shang Chang; Chuang-Chieh Lin; Peter Rossmanith
作品所屬單位
出版者
會議名稱International Workshop on Exact and Parameterized Computation (IWPEC 2008)
會議地點Victoria B.C., Canada
摘要Given a set of n taxa S, exactly one topology for every subset of four taxa, and a positive integer k as the parameter, 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(4^k n + n^4). In this paper, first we present an O(3.0446^k n + n^4) algorithm and an O(2.0162^k n^3 + n^5) algorithm. Finally, we give an O *((1 + ε)^k ) algorithm with an arbitrarily small constant ε> 0.
關鍵字Search Tree; Evolutionary Tree; Polynomial Time Approximation Scheme; Path Structure; Branch Node
語言英文(美國)
收錄於
會議性質國際
校內研討會地點
研討會時間20080514~20080516
通訊作者
國別加拿大
公開徵稿
出版型式
出處Lecture Notes in Computer Science 5018, pp. 66–77
相關連結
SDGs
  • 優質教育
Google+ 推薦功能,讓全世界都能看到您的推薦!