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