%0 Journal Article
%T 翻转距离星树问题的计算复杂度和近似算法
%A 朱大铭
%A 雷鹏
%A 马绍汉
%J -
%D 2002
%X 讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2
%K 算法 进化树 基因组 NP-完全性 近似性能比
%U http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=20020612&flag=1