Graph triangulations and the compatibility of unrooted phylogenetic trees

DOI10.1016/J.AML.2010.12.015MaRDI QIDQ628277zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 437536 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A characterisation of rigid circuit graphs
• Compatibility of unrooted phylogenetic trees is FPT
• 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
• Quartet compatibility and the quartet graph
• The complexity of reconstructing trees from qualitative characters and subtrees

Cited in

(8)

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

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)