Fast compatibility testing for rooted phylogenetic trees

DOI10.1007/s00453-017-0330-4zbMath1392.68451OpenAlexW2963592740MaRDI QIDQ724246

Yun Deng, David Fernández Baca

Publication date: 25 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6088/

zbMATH Keywords

algorithmscomputational biologyphylogenetics

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problems related to evolution (92D15)

Related Items

Best match graphs ⋮ Corrigendum to: ``Best match graphs ⋮ Best match graphs with binary trees ⋮ Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study ⋮ Treewidth of display graphs: bounds, brambles and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Compatibility of unrooted phylogenetic trees is FPT
• The complexity of reconstructing trees from qualitative characters and subtrees
• Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
• Fast compatibility testing for phylogenies with nested taxa
• A characterisation of rigid circuit graphs
• Closure operations in phylogenetics
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Near-optimal fully-dynamic graph connectivity
• An On-Line Edge-Deletion Problem
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Incomplete Directed Perfect Phylogeny
• Fast Compatibility Testing for Rooted Phylogenetic Trees
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms