An \(O(n \log n)\) time algorithm for computing the path-length distance between trees

DOI10.1007/s00453-019-00594-5zbMath1429.68325arXiv1811.00619OpenAlexW2962920712MaRDI QIDQ2319639

Celine Scornavacca, David Bryant

Publication date: 20 August 2019

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

tree decompositionphylogenytree comparison metricspath-length metric

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Problems related to evolution (92D15) Nonnumerical algorithms (68W05) Distance in graphs (05C12)

Cites Work

• Unnamed Item
• Unnamed Item
• Comparison of phylogenetic trees
• Dynamic expression trees
• Computing the quartet distance between evolutionary trees in time \(O(n\,\log n)\)
• The Parallel Evaluation of General Arithmetic Expressions

This page was built for publication: An \(O(n \log n)\) time algorithm for computing the path-length distance between trees