Fixed-Parameter Algorithms for Finding Agreement Supertrees

DOI10.1137/120897559zbMath1314.05200OpenAlexW2002741458MaRDI QIDQ5252691

Sylvain Guillemot, Brad Shutters, Sudheer R. Vakati, David Fernández Baca

Publication date: 2 June 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/795a20c3972237a14f1a5656b3f66511c72d87a8

zbMATH Keywords

computational biologyagreementfixed-parameter algorithmsphylogenies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Trees (05C05) Problems related to evolution (92D15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Constructing a Consensus Phylogeny from a Leaf-Removal Distance (Extended Abstract) ⋮ On compatibility and incompatibility of collections of unrooted phylogenetic trees ⋮ A decomposition theorem and two algorithms for reticulation-visible networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved algorithms for maximum agreement and compatible supertrees
• Rooted maximum agreement supertrees
• Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
• The complexity of reconstructing trees from qualitative characters and subtrees
• Finding largest subtrees and smallest supertrees
• Phylogenetic supertrees. Combining information to reveal the tree of life
• Reconstruction of rooted trees from subtrees
• Maximum agreement and compatible supertrees
• Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• The Complexity of Multiterminal Cuts
• Multicut is FPT
• Fixed-parameter tractability of multicut parameterized by the size of the cutset

This page was built for publication: Fixed-Parameter Algorithms for Finding Agreement Supertrees