The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete
المؤلفون المشاركون
Cardona, Gabriel
Llabrés, Mercè
Rosselló, Francesc
Valiente, Gabriel
المصدر
العدد
المجلد 2014، العدد 2014 (31 ديسمبر/كانون الأول 2014)، ص ص. 1-6، 6ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2014-04-02
دولة النشر
مصر
عدد الصفحات
6
التخصصات الرئيسية
الطب البشري
تكنولوجيا المعلومات وعلم الحاسوب
الملخص EN
Several polynomial time computable metrics on the class of semibinary tree-sibling time consistent phylogenetic networks are available in the literature; in particular, the problem of deciding if two networks of this kind are isomorphic is in P.
In this paper, we show that if we remove the semibinarity condition, then the problem becomes much harder.
More precisely, we prove that the isomorphism problem for generic tree-sibling time consistent phylogenetic networks is polynomially equivalent to the graph isomorphism problem.
Since the latter is believed not to belong to P, the chances are that it is impossible to define a metric on the class of all tree-sibling time consistent phylogenetic networks that can be computed in polynomial time.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Cardona, Gabriel& Llabrés, Mercè& Rosselló, Francesc& Valiente, Gabriel. 2014. The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete. The Scientific World Journal،Vol. 2014, no. 2014, pp.1-6.
https://search.emarefa.net/detail/BIM-1048920
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Cardona, Gabriel…[et al.]. The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete. The Scientific World Journal No. 2014 (2014), pp.1-6.
https://search.emarefa.net/detail/BIM-1048920
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Cardona, Gabriel& Llabrés, Mercè& Rosselló, Francesc& Valiente, Gabriel. The Comparison of Tree-Sibling Time Consistent Phylogenetic Networks Is Graph Isomorphism-Complete. The Scientific World Journal. 2014. Vol. 2014, no. 2014, pp.1-6.
https://search.emarefa.net/detail/BIM-1048920
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1048920
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر