Graph triangulations and the compatibility of unrooted phylogenetic trees

DOI10.1016/J.AML.2010.12.015zbMATH Open1209.05055OpenAlexW1817952903MaRDI QIDQ628277FDOQ628277

Authors: Sudheer Vakati, David Fernández-Baca 

Publication date: 10 March 2011

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aml.2010.12.015

Recommendations

• Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors
• On compatibility and incompatibility of collections of unrooted phylogenetic trees
• Extension operations on sets of leaf-labelled trees
• Minimal Triangulation Algorithms for Perfect Phylogeny Problems
• Fast compatibility testing for rooted phylogenetic trees

zbMATH Keywords

phylogeneticschordal graphscompatibilitysupertreestree decompositionsgraph triangulation

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• The complexity of reconstructing trees from qualitative characters and subtrees
• Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Compatibility of unrooted phylogenetic trees is FPT
• A characterisation of rigid circuit graphs
• Quartet compatibility and the quartet graph
• Title not available (Why is that?)

Cited In (9)

• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• Algorithms and Computation
• Treewidth distance on phylogenetic trees
• Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors
• Treewidth of display graphs: bounds, brambles and applications
• Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees
• On compatibility and incompatibility of collections of unrooted phylogenetic trees
• Phylogeny numbers for graphs with two triangles
• On the ancestral compatibility of two phylogenetic trees with nested taxa

This page was built for publication: Graph triangulations and the compatibility of unrooted phylogenetic trees

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