Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The comparison of tree-sibling time consistent phylogenetic networks is graph isomorphism-complete

Autor
Cardona, G.; Llabrés, M.; Rossello, F.; Valiente, G.
Tipus d'activitat
Article en revista
Revista
The scientific world journal
Data de publicació
2014-01-01
Volum
2014
Número
Article ID 254279
Pàgina inicial
1
Pàgina final
6
DOI
https://doi.org/10.1155/2014/254279 Obrir en finestra nova
URL
http://www.hindawi.com/journals/tswj/2014/254279/ Obrir en finestra nova
Resum
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 ...
Paraules clau
Metrics
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants