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

標題:Testing consistency of quartet topologies: a parameterized approach
學年102
學期1
出版(發表)日期2013/11/30
作品名稱Testing consistency of quartet topologies: a parameterized approach
作品名稱(其他語言)
著者Maw-Shang Chang; Chuang-Chieh Lin; Peter Rossmanith
單位
出版者
著錄名稱、卷期、頁數Information Processing Letters 113(22-24), pp. 852-857
摘要Property testing considers the following task: given a function ψ over a domain D, a property P and a parameter 0 < \epsilon < 1, by querying function values of f over
o(|D|) elements in D, determine if ψ satisfies P or differs from any one which satisfies P in at least \epsilon |D| elements. We focus on consistency of quartet topologies. Given a set Q of quartet topologies over an n-taxon set and an upper bound k on the number of quartets whose topologies are missing, we present a non-adaptive property tester with one-sided error, which runs in time O(1.7321^k kn^3/\epsilon) and uses queries, to test if Q is consistent with an evolutionary tree.
關鍵字Randomized algorithm;Property testing;Evolutionary tree;Quartet method
語言英文(美國)
ISSN1872-6119
期刊性質國外
收錄於SCI;
產學合作
通訊作者Chuang-Chieh Lin
審稿制度
國別美國
公開徵稿
出版型式,電子版,紙本
相關連結
SDGs
  • 優質教育
Google+ 推薦功能,讓全世界都能看到您的推薦!