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
語言 en_US
收錄於
會議性質 國際
校內研討會地點 無
研討會時間 20080514~20080516
通訊作者
國別 CAN
公開徵稿
出版型式
出處 Lecture Notes in Computer Science 5018, pp. 66–77
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/120186 )

SDGS 優質教育