The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics

DOI10.1016/j.tcs.2018.08.006zbMath1410.68172arXiv1803.05866OpenAlexW2962842745MaRDI QIDQ1713404

Nadia El-Mabrouk, Manuel Lafond, Vincent L. Moulton, Katharina T. Huber

Publication date: 25 January 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.05866

zbMATH Keywords

NP-hardnessphylogenetic treefixed-parameter tractabilitytree shapemultilabelled tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Problems related to evolution (92D15)

Related Items (2)

Autopolyploidy, allopolyploidy, and phylogenetic networks with horizontal arcs ⋮ The ultrametric Gromov-Wasserstein distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Folding and unfolding phylogenetic trees and networks
• The agreement metric for labeled binary trees
• On the agreement of many trees
• On the approximation of largest common subtrees and largest common point sets
• The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
• Phylogenetic networks from multi-labelled trees
• Computing the Gromov-Hausdorff Distance for Metric Trees
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• Comparison of labeled trees with valency three

This page was built for publication: The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics