Graph triangulations and the compatibility of unrooted phylogenetic trees

DOI10.1016/j.aml.2010.12.015zbMath1209.05055OpenAlexW1817952903MaRDI QIDQ628277

David Fernández Baca, Sudheer R. Vakati

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

chordal graphstree decompositionscompatibilityphylogeneticssupertreesgraph triangulation

Mathematics Subject Classification ID

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

Related Items

Treewidth distance on phylogenetic trees ⋮ Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors ⋮ On compatibility and incompatibility of collections of unrooted phylogenetic trees ⋮ Treewidth of display graphs: bounds, brambles and applications

Cites Work

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