On the computational complexity of the rooted subtree prune and regraft distance
From MaRDI portal
Publication:1764471
DOI10.1007/s00026-004-0229-zzbMath1059.05035OpenAlexW1982901388WikidataQ104141373 ScholiaQ104141373MaRDI QIDQ1764471
Magnus Bordewich, Charles Semple
Publication date: 25 February 2005
Published in: Annals of Combinatorics (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/613/1/613.pdf
Related Items (53)
Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees ⋮ Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations ⋮ Approximating geodesic tree distance ⋮ Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees ⋮ Bounding the number of hybridisation events for a consistent evolutionary history ⋮ Distance metrics for ranked evolutionary trees ⋮ Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks ⋮ A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees ⋮ Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph ⋮ Computing the minimum number of hybridization events for a consistent evolutionary history ⋮ On the complexity of computing MP distance between binary phylogenetic trees ⋮ Hypercubes and Hamilton cycles of display sets of rooted phylogenetic networks ⋮ Exploring spaces of semi-directed level-1 networks ⋮ The agreement distance of unrooted phylogenetic networks ⋮ Extremal distances for subtree transfer operations in binary trees ⋮ The asymmetric cluster affinity cost ⋮ Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance ⋮ Gene tree reconciliation including transfers with replacement is NP-hard and FPT ⋮ A near-linear kernel for bounded-state parsimony distance ⋮ A duality based 2-approximation algorithm for maximum agreement forest ⋮ Haplotype Inferring Via Galled-Tree Networks Is NP-Complete ⋮ Properties for the Fréchet mean in Billera-Holmes-Vogtmann treespace ⋮ Walks in phylogenetic treespace ⋮ Ranked subtree prune and regraft ⋮ A quadratic kernel for computing the hybridization number of multiple trees ⋮ A cluster reduction for computing the subtree distance between phylogenies ⋮ Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees ⋮ A scalable parallelization of the gene duplication problem ⋮ On a matching distance between rooted phylogenetic trees ⋮ On the subnet prune and regraft distance ⋮ On the fixed parameter tractability of agreement-based phylogenetic distances ⋮ Computing nearest neighbour interchange distances between ranked phylogenetic trees ⋮ Discrete coalescent trees ⋮ Unnamed Item ⋮ An analytical upper bound on the minimum number of recombinations in the history of SNP sequences in populations ⋮ Rotation distance is fixed-parameter tractable ⋮ Exploring the tiers of rooted phylogenetic network space using tail moves ⋮ Approximating maximum agreement forest on multiple binary trees ⋮ Algorithms for parameterized maximum agreement forest problem on multiple trees ⋮ An Improved Approximation Algorithm for rSPR Distance ⋮ A 3-approximation algorithm for the subtree distance between phylogenies ⋮ Efficiently Calculating Evolutionary Tree Measures Using SAT ⋮ Note on the hybridization number and subtree distance in phylogenetics ⋮ Better Practical Algorithms for rSPR Distance and Hybridization Number ⋮ Overlaid species forests ⋮ A new recombination lower bound and the minimum perfect phylogenetic forest problem ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees ⋮ Heading in the right direction? Using head moves to traverse phylogenetic network space ⋮ Computing Maximum Agreement Forests without Cluster Partitioning is Folly ⋮ Faster exact computation of rSPR distance ⋮ A parsimony-based metric for phylogenetic trees ⋮ A New Algorithm for Inferring Hybridization Events Based on the Detection of Horizontal Gene Transfers ⋮ On the maximum parsimony distance between phylogenetic trees
This page was built for publication: On the computational complexity of the rooted subtree prune and regraft distance
