Algorithms for parameterized maximum agreement forest problem on multiple trees

DOI10.1016/J.TCS.2013.12.025zbMATH Open1382.68181OpenAlexW2048978656MaRDI QIDQ744101FDOQ744101

Authors: Feng Shi, Jianxin Wang, Qilong Feng, Jiong Guo, Jianer Chen 

Publication date: 6 October 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.12.025

Recommendations

• Parameterized algorithms for maximum agreement forest on multiple trees
• Approximation algorithms for maximum agreement forest on multiple trees
• Approximating maximum agreement forest on multiple binary trees
• Parameterized and approximation algorithms for the MAF problem in multifurcating trees
• A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees

zbMATH Keywords

phylogenetic treefixed-parameter tractabilitymaximum agreement forest

Mathematics Subject Classification ID

Problems related to evolution (92D15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Fixed-parameter algorithms for maximum agreement forests
• Comparison of phylogenetic trees
• On the computational complexity of the rooted subtree prune and regraft distance
• Subtree transfer operations and their induced metrics on evolutionary trees
• On the complexity of comparing evolutionary trees
• The maximum agreement forest problem: Approximation algorithms and computational experiments
• A 3-approximation algorithm for the subtree distance between phylogenies
• Title not available (Why is that?)
• Faster Exact Computation of rSPR Distance
• A faster FPT algorithm for the maximum agreement forest problem
• Approximating the maximum agreement forest on \(k\) trees
• Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees

Cited In (5)

• Approximating maximum agreement forest on multiple binary trees
• Kernelization and parameterized algorithms for covering a tree by a set of stars or paths
• A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
• Approximating the maximum agreement forest on \(k\) trees
• A faster FPT algorithm for the maximum agreement forest problem

This page was built for publication: Algorithms for parameterized maximum agreement forest problem on multiple trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744101)