An Improved Approximation Algorithm for rSPR Distance

DOI10.1007/978-3-319-42634-1_38zbMath1476.68199OpenAlexW2502242661MaRDI QIDQ2817889

Lusheng Wang, Eita MacHida, Zhi-Zhong Chen

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-42634-1_38

Mathematics Subject Classification ID

Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Approximation algorithms (68W25)

Related Items (3)

A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees ⋮ A duality based 2-approximation algorithm for maximum agreement forest ⋮ Better Practical Algorithms for rSPR Distance and Hybridization Number

Uses Software

• FastHN
• rSPR

Cites Work

• Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees
• A 3-approximation algorithm for the subtree distance between phylogenies
• The maximum agreement forest problem: Approximation algorithms and computational experiments
• Fitting distances by tree metrics with increment error
• On the computational complexity of the rooted subtree prune and regraft distance
• Faster exact computation of rSPR distance
• Bounding the number of hybridisation events for a consistent evolutionary history
• On the complexity of comparing evolutionary trees

This page was built for publication: An Improved Approximation Algorithm for rSPR Distance