On the fixed parameter tractability of agreement-based phylogenetic distances
DOI10.1007/S00285-016-1023-3zbMATH Open1354.05129OpenAlexW2407777965WikidataQ50639269 ScholiaQ50639269MaRDI QIDQ504072FDOQ504072
Magnus Bordewich, N. Tokac, Celine Scornavacca, Mathias Weller
Publication date: 25 January 2017
Published in: Journal of Mathematical Biology (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/18815/1/18815.pdf
Recommendations
- Fixed-parameter algorithms for maximum agreement forests
- A cluster reduction for computing the subtree distance between phylogenies
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- Reduction rules for the maximum parsimony distance on phylogenetic trees
- Treewidth distance on phylogenetic trees
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational methods for problems pertaining to biology (92-08)
Cites Work
- Fixed-parameter algorithms for maximum agreement forests
- On the computational complexity of the rooted subtree prune and regraft distance
- Title not available (Why is that?)
- Subtree transfer operations and their induced metrics on evolutionary trees
- On the complexity of comparing evolutionary trees
- A cluster reduction for computing the subtree distance between phylogenies
- Bounding the number of hybridisation events for a consistent evolutionary history
- Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
- Computing the minimum number of hybridization events for a consistent evolutionary history
- Fast Algorithms for Finding Nearest Common Ancestors
- Inferring a level-1 phylogenetic network from a dense set of rooted triplets
- When two trees go to war
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- Faster exact computation of rSPR distance
- Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees
Cited In (13)
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- Exploring the tiers of rooted phylogenetic network space using tail moves
- Scanning Phylogenetic Networks Is NP-hard
- Computing Maximum Agreement Forests without Cluster Partitioning is Folly
- Treewidth distance on phylogenetic trees
- A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees
- On the hardness of inferring phylogenies from triplet-dissimilarities
- Treewidth of display graphs: bounds, brambles and applications
- Reflections on kernelizing and computing unrooted agreement forests
- The agreement distance of unrooted phylogenetic networks
- New reduction rules for the tree bisection and reconnection distance
- Title not available (Why is that?)
This page was built for publication: On the fixed parameter tractability of agreement-based phylogenetic distances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q504072)
